Nosso problema parece ter sido causado por um número moderadamente alto de solicitações recebidas.
Assim que o número de conexões não autenticadas passar pelo parâmetro sshd: MaxStartUps, O sshd começa a rejeitar essas conexões.
A solução está em modificar MaxStartups
em sshd_config