A chave do host mais provável foi alterada, não o par de chaves pública / privada ssh.
Todas as chaves do host devem ser exclusivas, até mesmo clones, exceto em certos cenários de alta disponibilidade, então a Amazon provavelmente regenera essas configurações após a clonagem.
Você só precisa remover a linha em seu arquivo ~ / .ssh / known_hosts e estará pronto.