Before tweaks ============= Standard installations, no intentional tweaks despite "UseDNS no". All VMs run on the same host using KVM. Arch Linux (openssh-6.8p1-2): $ time for i in {1..100}; do ssh overqemu00 /bin/true; done real 0m9.904s user 0m1.300s sys 0m0.123s Ubuntu 12.04 (openssh-server-5.9p1-5ubuntu1.4): $ time for i in {1..100}; do ssh overqemu01 /bin/true; done real 0m34.388s user 0m0.797s sys 0m0.130s Ubuntu 14.04 (openssh-server-6.6p1-2ubuntu2): $ time for i in {1..100}; do ssh overqemu02 /bin/true; done real 0m32.895s user 0m1.340s sys 0m0.133s CentOS 7 (openssh-6.6.1p1-11.el7): $ time for i in {1..100}; do ssh overqemu05 /bin/true; done real 0m18.580s user 0m1.093s sys 0m0.133s For further reference: OpenBSD 5.6 (openssh-6.7): $ time for i in {1..100}; do ssh overqemu03 /usr/bin/true; done real 0m8.871s user 0m1.293s sys 0m0.113s FreeBSD 10.1 (openssh-6.6.1p1): $ time for i in {1..100}; do ssh overqemu04 /usr/bin/true; done real 0m8.876s user 0m1.483s sys 0m0.200s After tweaks ============ What has been changed? - Cleared /etc/update-motd.d on Ubuntu. PAM runs all these scripts on each login. Ubuntu 12.04: $ time for i in {1..100}; do ssh overqemu01 /bin/true; done real 0m6.884s user 0m0.850s sys 0m0.170s Ubuntu 14.04: $ time for i in {1..100}; do ssh overqemu02 /bin/true; done real 0m8.452s user 0m1.490s sys 0m0.187s