A quantidade atual de informações não é suficiente para diagnosticar seu problema. Você pode aumentar o detalhamento da conexão no servidor e no cliente, e essa saída pode incluir informações importantes para resolver seu problema.
No seu servidor, reinicie o ssh da seguinte forma:
sudo service ssh stop
sudo /usr/sbin/sshd -d
Isso inicia o servidor no modo debug , o que significa que ele não entra em segundo plano e produz mensagens de erro para o erro padrão.
No lado do servidor, você inicia a tentativa de conexão com
ssh me@remote_server -vvv
Quando você tiver essa saída, poste os bits relevantes aqui e várias pessoas poderão ajudá-lo (não apenas eu).