This might be fixed upstream according to the changelog. http://www.openssh.com/txt/release-6.9: * ssh(1), sshd(8): cap DH-GEX group size at 4Kbits for Cisco implementations as some would fail when attempting to use group sizes >4K; bz#2209 HTH, Simon