Clients see ssh_exchange_identification: Connection closed by remote host

This was an intermittent problem. One reason could be that ssh property MaxStartups has been reached. One of the servers we had was used by many remote users, and it was very slow at authenticating.

To verify the problem, edit /etc/ssh/sshd_config

Add the line LogLevel DEBUG2

Reload sshd, e.g. /etc/init.d/sshd reload

Check logs in /var/log/secure

If you see something like

Sep 10 20:43:13 bombay sshd[32237]: debug1: drop connection #10

It is because MaxStartups has been reached.

Once that is confirmed, edit /etc/ssh/sshd_config again

Remove the LogLevel DEBUG2, and add MaxStartups 50 (or whatever your needs are)

Reload sshd again.