Slow public key authentication with paramiko

Question

I am using paramiko to connect to a remote server via ssh. When using public key authentication, performance is slow (~ 90 seconds). Here is the relevant log output:

2012-05-14 17:37:21,378 Ciphers agreed: local=aes128-ctr, remote=aes128-ctr 2012-05-14 17:37:21,378 using kex diffie-hellman-group1-sha1; server key type ssh-rsa; cipher: local aes128-ctr, remote aes128-ctr; mac: local hmac-sha1, remote hmac-sha1; compression: local none, remote none 2012-05-14 17:37:21,481 Switch to new keys ... 2012-05-14 17:37:21,483 Adding ssh-rsa host key for 10.12.34.56: 8a05c68a0707a9fad19290c22542a338 2012-05-14 17:37:21,485 Trying discovered key 3793c7b9c500f52c12e190e92e21713f in /home/david/.ssh/id_rsa 2012-05-14 17:37:21,513 userauth is OK 2012-05-14 17:38:54,370 Authentication (publickey) successful! 

Note the delay between the last two lines of the log output. When using ssh to connect from the command line for the same user and remote server, the connection is instant. Any ideas what causes the delay?

Answer 1

After enough experimentation, it seems that the delay is related to the key length. The first key I used was 4096 bits. When I switched to a shorter (2048 bit) key, the time required for authentication was drastically reduced (<2 seconds).

Answer 2

pycrypto>=2.5 very slow. After downgrading to pycrypto==2.4.1 I saw an improvement of 25 times.