Use ssh-keygen -R hostname para remover o nome do host do seu arquivo known_hosts. Da próxima vez que você se conectar, a nova chave do host será adicionada ao seu arquivo known_hosts.
Se o sistema operacional de um host foi reinstalado e teve sua chave pública regenerada, isso obviamente falhará porque a nova chave não corresponde à antiga.
Existe uma maneira mais fácil de dizer ao ssh que você sabe que a chave do host foi alterada e que você deseja que ela seja atualizada. Acho que é um pouco propenso a erros usar um editor de texto ou algo parecido com sed para remover a linha ofensiva.
TARGET_HOST=[hostname or IP]
# Remove the old key(s) from known_hosts
ssh-keygen -R $TARGET_HOST
# Add the new key(s) to known_hosts (and also hash the hostname/address)
ssh-keyscan -H $TARGET_HOST >> ~/.ssh/known_hosts
Da próxima vez que você se conectar, conectará sem que seja solicitado Are you sure you want to continue connecting (yes/no)? , pois as chaves já estarão no arquivo known_hosts .
Tags ssh key-authentication