Same exact problem here to access a dedicated server at the online.net datacenter.
Theres no problem after a reboot, no need to change MTU, ssh connection works for 1-3 weeks, then appears this exact same bug , blocking on KEXINIT, no more possible to connect the ssh server.
It could be some kind of sshd bug, but its necessarily triggered by some nework stuff happening after 1-3 weeks, I reproduced this exact problem many times with many different servers on this network, some say it could be related to a cisco bug, possibly related with some DPI options.
That problem never happened with other servers I manage in other datacenters, and that have the exact same distro, config and sshd version .
if you dont want to reboot every 10 days because the datacenter firewalls ( or other network tweaks ) is doing weird stuff :
first connect with one of those client side workarounds :
workaround 1, lowering your local, client side MTU :
ip li set mtu 1400 dev wlan0
( 1400 should be enough but you can try to use lower values if needed )
workaround 2, specifying the chosen cypher for the ssh connection :
ssh -c firstname.lastname@example.org host
(or try with any another available cypher )
Both of those client side workarounds made it for me, I could connect and save my uptime; but you want to fix this server-side, forever, so you dont have to ask every client to locally tweak their MTU.
On gentoo i just added :
( same mtu option should be available somewhere in your preferred distro network config file )
I ve set the mtu to 1400, but 1460 is probably enough in most cases.
another helping workaround could be to use the following iptables rules to manage fragmentation :
# /sbin/iptables -I OUTPUT -p tcp --tcp-flags SYN,RST SYN -j TCPMSS --clamp-mss-to-pmtu
# /sbin/ip6tables -I OUTPUT -p tcp --tcp-flags SYN,RST SYN -j TCPMSS --clamp-mss-to-pmtu
( but I personaly didnt need this one until now )
also note that the symptoms of this problem can also be :
debug1: SSH2_MSG_KEXINIT sent
debug1: expecting SSH2_MSG_KEX_DH_GEX_REPLY
edit march 2016 :
lowering the mtu to 1400 on the server most always work, but I recently had the case where mtu was already lowered to 1400 on the server and the problem reappeared, and the client also had to lower mtu to 1400.
The problem also appeared on web login forms waiting for the page to reload until saying "the server have reset the connection", also fixed after the client set the mtU to 1400.
related links :