Problemas com as chaves rsa e dsa

Olá boa tarde!

Tenho tido problemas com um servidor, conectava normalmente via SSH e de uns dias para cá, apresenta o seguinte erro:
Autenticação de senha SSH falhou: Access denied. Authentication that can continue: publickey,gssapi-keyex,gssapi-with-mic,password

Após este problema, consegui remover as chaves, reiniciei o servidor e consegui um único acesso remoto, perdi a conexão e venho tendo o mesmo problema novamente.

Como posso fazer para resolver definitivamente esse conflito?

Obrigada