It is my understanding that in OpenSSH 7.x several changes regarding weak and legacy cryptography. (I ran into a similar problem upgrading OpenSSH on my home server.) Under "Potentially Incompatible Changes", this item may be to related:

* Support for ssh-dss, ssh-dss-cert-* host and user keys is disabled by default at run-time. These may be re-enabled using the instructions at http://www.openssh.com/legacy.html

The following links may be more informative:

• Using OpenSSH with legacy SSH implementations
• Release notes, OpenSSH 7.1
• Release notes, OpenSSH 7.0
• Release notes, OpenSSH 6.9
• Release notes, OpenSSH 6.8

Hope that helps.