Intermittent ssh_exchange_identification: Connection closed by remote host
Our issue appeared to have been caused by a moderately high number of incoming requests.
As soon as the number of unauthenticated connections goes over the sshd:MaxStartUps parameter, sshd starts rejecting those connections.
The solution lies in modifying MaxStartups in sshd_config