Quais opções do ssh você está usando? Se você ainda não é, você deve considerar os dois seguintes
-o StrictHostKeyChecking=no
-o UserKnownHostsFile=/dev/null
Você pode colocá-los em seu arquivo ~ / .ssh / config ou usá-los juntos na CLI.
A outra coisa que eu queria saber é que sua instância está terminando e sendo reprovada? Isso mudaria o ID do host. Apenas um pensamento.