Eu estava respondendo a perguntas semelhantes em Unix so para resumir, no OpenSSH 6.8+ existe a opção UpdateHostKeys
, que diz ao seu cliente que ele deve pegar todas as chaves do host oferecidas pelo servidor.
Isso deve resolver seus problemas.