時々サーバへSSH接続できなくなって、何度もトライしているうちに入れるというの繰り返していたのがやっと原因判明
結局のところ、MaxStartups が原因でした。

たしかに接続の多いサーバではあったので、MaxSessionsを増やしてみたけど解決しなくてずっと悩んでたのがやっと解決。

/var/log/secureへは下記のエラーが出力される

ssh_exchange_identification: Connection closed by remote host

sshd_configで、MaxStartups を増やしてあげれば治りました。

MaxStartups (最大起動数)
認証されていない段階の接続をSSH デーモンが最大でどれだけ受けつけるかを指定します。
この値を超えた (認証されていない段階の) 接続は捨てられます。
この状態は (すでに接続したクライアントの) 認証が成功するか、そのLoginGraceTime(ログイン猶予時間) が切れるまで続きます。

CentOS7 などのデフォルトでは 10:30:100になってて
非認証な接続が 10 を超えるとそれ以降の接続を 30% の確率で拒否し、さらに 100 に達した時点でそれ以降の接続を全て拒否する