ssh_exchange_identification: Connection closed by remote host

A user is reporting occasional SSH issues on our instance using Jenkins and I'm trying to dig to the bottom of it. The error is as follows:

Caused by: hudson.plugins.git.GitException: Command "git fetch --tags --progress git@domain.com:group/repo.git +refs/heads/*:refs/remotes/origin/*" returned status code 128:
stdout: 
stderr: ssh_exchange_identification: Connection closed by remote host
fatal: The remote end hung up unexpectedly

Running gitlab-ce-8.11.2-ce.1.el6.x86_64.rpm on RHEL 6.7 VM.

User has suggested the issue may be with MaxStartups in /etc/ssh/sshd_config which is currently set to default (commented out) but I'd like to find more details on if that is the issue before changing it. Might be fixable by #1471 (closed) if this error could be fixed by including better OpenSSH configs with omnibus.