I think the message is misleading, the RSA host key did not change.
A mensagem é válida. A chave em seu known_hosts
é DSA e o servidor envia RSA, eles diferem e está errado.
Desde o OpenSSH 6.8 o servidor envia todas as chaves após a autenticação para simplificar a rotação ou depreciação do hostkey.
Se você tiver um cliente e um servidor novos o suficiente, continue com a solução alternativa, aceite as chaves do DSA temporariamente e deixe o cliente escolher as novas:
ssh -oHostKeyAlgorithms=+ssh-dss your_remote_host
se o servidor tiver uma versão antiga, você precisará fazer isso manualmente, conforme explicado na pergunta.
Isso também precisa de um cliente configurado para aceitar as novas chaves: UpdateHostKeys yes
.