Проблема с долгим подключением из Ubuntu к другим компьютерам по ssh решилась редактированием файла /etc/nsswitch.conf так:

Ищем в файле строку:

hosts:             files   dns  и прочие параметры

Оставляем в ней только:

hosts:             files

Все! Начинает залетать с пол пинка 🙂