fail2ban を実行していますか?
denyhosts を実行していますか?
TCP 22 を許可する iptables はありますか?
sshd_config に「AllowUsers」を参照する行がありますか? (ほとんどはそうではありませんが、一部はそうです。あなたの場合は、その行にアカウントがリストされている必要があります)
このコマンドtail -f /var/log/secureをそのマシンで同時に実行しながら、2 番目のマシンからログインして問題を特定できますか? そうでない場合は、そのログの出力をここに貼り付けて、コメントしてください。
ロングショットですが、service sshd restartを試して、それが役立つかどうかをもう一度試してみてください. デーモンの再起動中にtail /varlog/messagesを実行して、実行中に何か異常を発見するかどうかを確認してください。問題を見つけた場合は、そうでない場合は、ここに出力を投稿してコメントしてください。
最後に、このcp /etc/ssh/sshd_config /etc/ssh/sshd_config.backを実行してから、別のマシンから既知の動作する sshd_config を取得し、それを自分のマシンの上に配置してから、デーモンを再起動して再試行します。
私のお金は、/var/log/secureで私たちを助けるものを見ることにかかっています。