Edite seu arquivo .ssh / known_hosts e exclua a linha correspondente à sua AMI.
O problema é que, na primeira vez em que você se conectou, o ssh salvou a chave remota daquela máquina à qual você se conectou e, quando ativou o Elastic IPs, essa chave remota mudou.