Existe um arquivo chamado known_hosts, normalmente no diretório de usuários ~/.ssh/ - contém as chaves que o ssh e outros serviços usam para autenticar as máquinas remotas às quais você se conecta.
Se a chave para um determinado servidor tiver sido atualizada, por exemplo, durante uma atualização do sistema operacional, uma nova chave para esse servidor será gerada nesse servidor. Como isso entra em conflito com a chave armazenada em sua máquina, o ssh perguntará se você ainda confia nessa máquina.
A primeira vez que você se conectar a uma máquina, o ssh perguntará se você confia nessa chave. Se você fizer isso, essa chave será copiada para o arquivo known_hosts para esse usuário.
Procure no arquivo known_hosts e remova a entrada da máquina remota. Agora, quando você se conectar, deverá ser solicitado a aceitar a nova chave. Movendo o arquivo, você provavelmente terá acionado a criação de um novo arquivo known_hosts para a primeira chave que você importou e terá perdido os registros da outra máquina a qual você pode ter conectado.