A chave ssh nunca é regenerada no mesmo host.
Você está vendo esta mensagem porque já tinha seu IP do Elastic conectado a uma instância completamente diferente.
Eu tenho uma instância no EC2 que acho que parei em um ponto ou outro. Quando eu reiniciei e tentei ssh, eu recebi essas mensagens sobre a chave do host ter mudado. Mas por quê?
É porque o Elastic IP que eu associei à instância teve que ser remapeado para ele?
A chave do host não deve ser gerada uma vez e não deve ser regenerada no mesmo host?
Tags ssh amazon-ec2