linux - Why is a TLS handshake taking *forever* (20 seconds) on a VPS?

I have a server that generally works fine, but gets stuck for 20 seconds when trying to connect with SSL (either SSH or HTTPS display the same pattern.)

I tried various connections without SSL, such as a telnet:

telnet server-name 80

Entered a GET command

GET http://server-name/
Host: server-name
Accept: text/html, */*
Accept-Language: en-us
User-Agent: Mozilla/4.0 (compatible; MSIE 6.0; Windows NT 5.1)

And the reply is 100% instantaneous.

However, when I try to connect to the server via HTTPS in my browser, or use SSH to connect to that same server, it sits for about 20 seconds before connecting.

For SSH, it will then work nicely (i.e. not slow at all anymore). For HTTPS, it will be slow each time it has to connect again. A connection that does not get closed will continue to work fast, however.

I'm adding a screenshot of the Net info appearing in Firebug. As we can see, each time a new connection is attempted, 20s. Looking at the server usage with htop, the CPU is at 0% and when something happens it goes to a whooping 0.01% for the 1 min. usage report. So the server overall is not being pegged in any way (i.e. it is a test server at this point and we do not get hits by others yet.)

So my question is: What could cause such a slowdown?

I thought maybe it could be that OpenSSL is attempting to use /dev/random, but I never heard of such a problem before. The random device does not output much at all on that VPS. However, /dev/urandom works very well. I can get 1Mb of random data in a few seconds. What could I look into to fix this problem?

---

/etc/resolv.conf looks like Google DNS. Should be fast...

# Dynamic resolv.conf(5) file for glibc resolver(3) generated by resolvconf(8)

#     DO NOT EDIT THIS FILE BY HAND -- YOUR CHANGES WILL BE OVERWRITTEN
nameserver 8.8.8.8
nameserver 8.8.4.4

Note that the Apache2 setup in itself should not matter directly since it also happens with SSH...

---

Also I tried with ssh -vvv. The connection is instantaneous.

OpenSSH_6.6.1, OpenSSL 1.0.1f 6 Jan 2014
debug1: Reading configuration data /home/alexis/.ssh/config
debug1: /home/alexis/.ssh/config line 202: Applying options for do-nia2match
debug1: Reading configuration data /etc/ssh/ssh_config
debug1: /etc/ssh/ssh_config line 19: Applying options for *
debug1: Hostname has changed; re-reading configuration
debug1: Reading configuration data /home/alexis/.ssh/config
debug1: Reading configuration data /etc/ssh/ssh_config
debug1: /etc/ssh/ssh_config line 19: Applying options for *

debug2: ssh_connect: needpriv 0
debug1: Connecting to 178.62.213.172 [178.62.213.172] port 22.
debug1: Connection established.
...
debug1: SSH2_MSG_NEWKEYS received
debug1: SSH2_MSG_SERVICE_REQUEST sent
debug2: service_accept: ssh-userauth
debug1: SSH2_MSG_SERVICE_ACCEPT received
debug2: key: /home/alexis/.ssh/do-nia2match_rsa, explicit


SUPER LONG PAUSE HAPPENS HERE (~20s)

debug1: Authentications that can continue: publickey,password
debug3: start over, passed a different list publickey,password
debug3: preferred publickey,keyboard-interactive
debug3: authmethod_lookup publickey
...

I'm not too sure why when sending the key the SSH server would hang for 20s...