1. UseDNS no в /etc/ssh/sshd_config — ускоряет логин в случае тормозного DNS. В моём случае стоял локальный кеширующий DNS, потому и так все было быстро.
2. Принудительное указание IPv4 в SSH клиенте — особо не помогло, видимо не у всех тормозит

И на askubuntu.com вопрос c bounty уныло провисел долгие недели без ответа…

Оказалось, используемый нашими дедами для реально полезных задач /etc/motd файл в Ubuntu используется весьма «креативно» — до 10-й версии motd перегенерировался по задаче crontab-а, которая выполняла кучу задач, в том числе и проверку обновлений на сервере canonical (и многое другое). Отключалось через 'update-motd --disable'. 

В 10-й версии это уже так просто не работает, т.к. генерацию motd перенесли в модули PAM, которые выполняются непосредственно в момент логина и отжирают эти самые драгоценные 2-3 секунды времени, пока пользователь в нетерпении смотрит на черное окно терминала. Итак, берем скальпель:

1. В файлах /etc/pam.d/login и /etc/pam.d/sshd выпиливаем начисто строчки «session optional pam_motd.so»
2. Сносим нафиг компоненты платного мониторинга, установленные по дефолту:
   aptitude remove landscape-client landscape-common

После этого можно наконец отредактировать по вкусу /etc/motd

В /etc/ssh/sshd_config смотрим, есть ли 'PrintMotd yes', если он вам все еще нужен.

Готово, логин на сервер теперь мгновенный :-)

PS. А если логинитесь с ключом, то RSA ключ проверяется быстрее чем DSA при равной длине (раза в 4) — и даже на современном железе на ключах от 2048 можно увидеть разницу.

Источник:
http://habrahabr.ru/blogs/linux/115942/