В новой версии openssh (7.0+) устарели ключи DSA и по умолчанию не используются ключи DSA (ни на сервере, ни на клиенте). Эти ключи больше не рекомендуется использовать, поэтому, если есть возможность, я бы рекомендовал использовать ключи RSA, где это возможно.
Если вам действительно нужно использовать ключи DSA, вам нужно явно разрешить их в конфигурации клиента с помощью
PubkeyAcceptedKeyTypes +ssh-dss
Достаточно поместить эту строку в ~/.ssh/config
, о чем вам пытается сообщить сообщение verbose.