DH GEX group out of range

If you want to use newer OpenSSH to connect to deprecated servers:

ssh -o KexAlgorithms=diffie-hellman-group14-sha1 -o HostKeyAlgorithms=+ssh-dss my.host.com

Add -v if you want to see what's happening, and -o HostKeyAlgorithms=ssh-dss if it still doesn't work:

ssh -v -o HostKeyAlgorithms=ssh-dss -o KexAlgorithms=diffie-hellman-group14-sha1 my.host.com

You can also, of course, edit /etc/ssh/ssh_config or ~/.ssh/ssh_config, and add:

Host my.host.com *.myinsecure.net 192.168.1.* 192.168.2.*
    HostKeyAlgorithms ssh-dss
    KexAlgorithms diffie-hellman-group1-sha1    

https://forum.ctwug.za.net/t/fyi-openssh-to-access-rbs-openssh-7/6069 mentions the following fix on Mikrotik Routerboards:

/ip ssh set strong-crypto=yes

(Noting this here because this answer also comes up on web searches when looking for a similar error message.)

If you want to use it over Git without editing your ssh_config or updating the SSH server:

GIT_SSH="ssh -oHostKeyAlgorithms=+ssh-dss -oKexAlgorithms=diffie-hellman-group14-sha1" git clone ssh://user@host/path-to-repository

It looks like you are running a newer OpenSSH client (OpenSSH 7.2p2) against an older OpenSSH server (OpenSSH 6.6.1p1). In the OpenSSH 7.1p2 release notes, it mentions:

• ssh(1), sshd(8): increase the minimum modulus size supported for diffie-hellman-group-exchange to 2048 bits.

From the error message reported, it looks like it is your client which is refusing the DH group exchange value presented by the _server.

Thus I am wondering if the "sudden issue" started happening around the time when your client machine had some packages/updates applied.

According to this SecurityExchange post, which describes a very similar issue, the "solution" may be to a) modify the /etc/ssh/moduli file on the server end such that the server does not use DH groups smaller than 2048 bits, or b) upgrade the server to OpenSSH 7.1p2 or later.