For those who have just updated to macOS Sierra, the default SSH client configuration is to not allow ssh-dss keys any longer.

Follow these instructions to update your keys.