Isso geralmente indica que a chave do host em seu arquivo known_hosts e aquela entregue a você pelo servidor não corresponde.
Isso pode significar duas coisas: que a chave do servidor de fato mudou (se a reinstalou, por exemplo), ou que há de fato um ataque de "homem no meio" acontecendo.
A melhor maneira de garantir é entrar em contato com o administrador do servidor e informá-lo sobre a mensagem de erro, perguntando se ele sabe sobre essa alteração de chave. Se ele não sabe nada, você pode querer ser cauteloso sobre a conexão com o servidor.
Geralmente o que você faz aqui é:
ssh-keygen -R server.name
para remover a entrada antiga. Percebo que você já está fazendo isso, então não tenho certeza do que está acontecendo aqui. No entanto, o fato de você estar fazendo isso sugere que você foi instruído a fazê-lo, o que também pode indicar que a chave do servidor realmente muda periodicamente.
Uma coisa é tentar desativar a verificação da chave do host (não recomendado, mas se você estiver fazendo a conexão do servidor para si mesmo, acho que deve ser relativamente seguro):
ssh -o 'StrictHostKeyChecking=no' ssh-server.example.com
Note que, se isso funcionar, por favor, NÃO faça disso o padrão, pois não é seguro; em vez disso, informe ao administrador do servidor sobre isso, porque isso pode ser um problema com o servidor e suas principais informações.
Leia aqui algumas boas informações sobre a verificação da chave do host ssh:
link