The OpenSSH website has the page dedicated to the legacy issues such as the above one. It suggests the below approach, on ta client:
ssh -oKexAlgorithms=+diffie-hellman-group1-sha1 184.108.40.206
Or more permanently you can add
This will help you in enabling your old algorithms on a client, by allowing it to simply connect to a server.
My problem was similar to your problem I had many (legacy) clients connecting to the recently upgraded server (i.e. ubuntu 14 -> ubuntu 16).
My change from openssh6 -> openssh7 completely disabled by default a
diffie-hellman-group1-sha1 key exchange method.
After doing lot of research I came up with my changes which I needed to do to a
/etc/ssh/sshd_config file as below :
And the more wide legacy set of changes as below:
It resolved my issue.