Algumas partes do openssh estão usando hashes MD5, e algumas estão usando hashes SHA256. No seu caso, parece que seu cliente está fornecendo um hash md5, enquanto seu servidor ssh-keygen nos usando SHA256.
Você pode calcular o hash sozinho. Se você obtiver a chave do host do arquivo .pub, será assim, reticências para substituir muitos caracteres:
AAAAB3[...]==
Então você mesmo pode fazer os hashes:
md5:
echo "AAAAB3[...]==" | base64 -d | md5sum
679e19234b295ee432a3920c30fda6ac
sha:
echo "AAAAB3[...]==" | base64 -d | sha1sum
41a53770303a0776a1378239e2ee0fd825705c74