How to enable diffie-hellman-group1-sha1 key exchange on Debian 8.0?

The OpenSSH website has a page dedicated to legacy issues such as this one. It suggests the following approach, on the client:

ssh -oKexAlgorithms=+diffie-hellman-group1-sha1 123.123.123.123

or more permanently, adding

Host 123.123.123.123
    KexAlgorithms +diffie-hellman-group1-sha1

to ~/.ssh/config.

This will enable the old algorithms on the client, allowing it to connect to the server.

I tried this solution, but my problem was that I had many (legacy) clients connecting to my recently upgraded server (ubuntu 14 -> ubuntu 16).

The change from openssh6 -> openssh7 disabled by default the diffie-hellman-group1-sha1 key exchange method.

After reading this and this I came up with the changes I needed to do to the /etc/ssh/sshd_config file:

#Legacy changes
KexAlgorithms +diffie-hellman-group1-sha1
Ciphers +aes128-cbc

But a more wide legacy set of changes is (taken from here)

#Legacy changes
KexAlgorithms diffie-hellman-group1-sha1,[email protected],ecdh-sha2-nistp256,ecdh-sha2-nistp384,ecdh-sha2-nistp521,diffie-hellman-group-exchange-sha256,diffie-hellman-group14-sha1
Ciphers 3des-cbc,blowfish-cbc,aes128-cbc,aes128-ctr,aes256-ctr