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
related links :