При подключении может остановиться на несколько секунд или десятков секунд. После чего подключение продолжается.
Ошибка связана с GSSAPI, для устранения тормозов его нужно отключить в ~/.ssh/config
GSSAPIAuthentication no

Обходной путь указан здесь: bugs.launchpad.net/ubuntu/+source/openssh/+bug/...
и связанный багрепорт: bugs.launchpad.net/openssh/+bug/84899

У кого есть желание, проголосуйте за них и/или напишите комментарий. Может пофиксят.