talvez um problema relacionado a impressões digitais / chaves corrompidas
As impressões digitais ou as chaves foram corrompidas (você editou manualmente um desses arquivos?). Remova a impressão digital do lado do servidor (nos clientes): ~ / .ssh / known_hosts e tente novamente. Quando você se reconectar, será solicitado a aceitar a chave do host novamente.
Se você conseguir acessar a máquina, talvez queira fazer uma cópia e recriar o lado do servidor ~ / .ssh / authorized_keys.
Então você tem que reiniciar o sshd
[EDITAR] talvez um problema hosts.allow? inspecionar o arquivo no servidor para ver que o sshd é permitido para todas as fontes grep sshd /etc/hosts.allow sshd: ALL