Ao tentar acessar um servidor através do SSH exibe esta mensagem:
WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED!

No meu caso aconteceu porque eu estava acessando um servidor com o IP Fixo, e eu refiz o servidor e coloquei o mesmo IP, ao acessar ele deu o erro, isso acontece porque seu computador armazenou a chave pública dele e o IP em um arquivo, o nome do arquivo é: known_hosts e geralmente fica dentro da pasta oculta do ssh no seu perfil.

Localize o arquivo:

# locate known_hosts
/root/.ssh/known_hosts

O arquivo foi encontrado dentro do diretório root, porque eu estava conectado como root.

# vim /root/.ssh/known_hosts

Dentro do arquivo vai estar o número de ip e em seguida a chave pública do ssh, basta apagar tudo e tentar novamente que o problema será resolvido. 😉