Openssh 7.0, released 2015-08-11, deprecated the use of DSA (ssh-dss) keys and RSA keys smaller than 1024 bits [0]. We have been applying some backwards compatibility configuration changes to ssh bastion servers in both Cloud VPS and Toolforge for some time to continue to support old keys using these deprecated algorithms. I was supposed to announce this to the community about 1.5 years ago, but apparently I did not [1].
We have noticed with the introduction of Debian Stretch ssh bastion servers running Openssh 7.4 that users with DSA keys (and possibly short RSA keys) are being denied access by the newer software. The easiest fix for this is for users to generate new keys and upload their new public key using the form at https://toolsadmin.wikimedia.org/profile/settings/ssh-keys or https://wikitech.wikimedia.org/wiki/Special:Preferences#mw-prefsection-openstack.
We currently recommend using either ed25519 or 4096-bit RSA keys. See https://wikitech.wikimedia.org/wiki/Production_shell_access#Generating_your_SSH_key for more information.
[0]: https://www.openssh.com/txt/release-7.0 [1]: https://phabricator.wikimedia.org/T168433
Bryan, on behalf of the Wikimedia Cloud Services team