Linux TCP connection establishment is very slow

I'm not sure what's wrong, but every outgoing network connection is very slow on my server (called dikkenek in the snippets below). It seems it's at the connection establishment.

bicou@dikkenek:~$ time ping -c 1 free.fr
PING free.fr (212.27.48.10) 56(84) bytes of data.
64 bytes from www.free.fr (212.27.48.10): icmp_seq=1 ttl=58 time=12.1 ms

--- free.fr ping statistics ---
1 packets transmitted, 1 received, 0% packet loss, time 0ms
rtt min/avg/max/mdev = 12.185/12.185/12.185/0.000 ms

real    0m10.025s
user    0m0.000s
sys     0m0.000s

As you can see the connection is perfectly fine (12ms to my ISP home page), however it took 10 seconds to run the ping.

Pinging directly the IP is much faster:

bicou@dikkenek:~$ time ping -c 1 212.27.48.10
PING 212.27.48.10 (212.27.48.10) 56(84) bytes of data.
64 bytes from 212.27.48.10: icmp_seq=1 ttl=58 time=12.0 ms

--- 212.27.48.10 ping statistics ---
1 packets transmitted, 1 received, 0% packet loss, time 0ms
rtt min/avg/max/mdev = 12.045/12.045/12.045/0.000 ms

real    0m0.013s
user    0m0.000s
sys     0m0.000s

So I thought I had a name resolution issue, but it's fast too:

bicou@dikkenek:~$ time host free.fr
free.fr has address 212.27.48.10
free.fr has IPv6 address 2a01:e0c:1::1
free.fr mail is handled by 20 mx2.free.fr.
free.fr mail is handled by 10 mx1.free.fr.

real    0m3.022s
user    0m0.008s
sys     0m0.000s

OK, it took 3 seconds, but that's not longer than a fast machine, see below.

As a comparison, here are the same commands ran on my laptop (Mac OS X):

<9> Mon May 11 23:05:42 ~ $ time ping -c 1 free.fr
PING free.fr (212.27.48.10): 56 data bytes
64 bytes from 212.27.48.10: icmp_seq=0 ttl=58 time=15.194 ms

--- free.fr ping statistics ---
1 packets transmitted, 1 packets received, 0.0% packet loss
round-trip min/avg/max/stddev = 15.194/15.194/15.194/0.000 ms

real    0m0.026s
user    0m0.001s
sys     0m0.003s
<10> Mon May 11 23:05:48 ~ $ time ping -c 1 212.27.48.10
PING 212.27.48.10 (212.27.48.10): 56 data bytes
64 bytes from 212.27.48.10: icmp_seq=0 ttl=58 time=44.084 ms

--- 212.27.48.10 ping statistics ---
1 packets transmitted, 1 packets received, 0.0% packet loss
round-trip min/avg/max/stddev = 44.084/44.084/44.084/0.000 ms

real    0m0.060s
user    0m0.001s
sys     0m0.003s
<11> Mon May 11 23:06:09 ~ $ time host free.fr
free.fr has address 212.27.48.10
free.fr has IPv6 address 2a01:e0c:1::1
free.fr mail is handled by 20 mx2.free.fr.
free.fr mail is handled by 10 mx1.free.fr.

real    0m3.059s
user    0m0.006s
sys     0m0.006s

The ping is much faster.

Simple HTTP connections are very slow too:

bicou@dikkenek:~$ time curl -sI 'free.fr'
HTTP/1.1 302 Moved Temporarily
Server: nginx
Date: Mon, 11 May 2015 21:10:47 GMT
Content-Type: text/html
Content-Length: 154
Connection: keep-alive
Location: http://portail.free.fr/


real    0m5.548s
user    0m0.008s
sys     0m0.000s

My laptop:

<14> Mon May 11 23:08:11 ~ $ time curl -sI 'free.fr'
HTTP/1.1 302 Moved Temporarily
Server: nginx
Date: Mon, 11 May 2015 21:12:04 GMT
Content-Type: text/html
Content-Length: 154
Connection: keep-alive
Location: http://portail.free.fr/


real    0m0.043s
user    0m0.005s
sys     0m0.004s

An iperf between the two (both ways) is perfectly fine:

bicou@dikkenek:~$ iperf -c 192.168.0.13 -r
------------------------------------------------------------
Server listening on TCP port 5001
TCP window size: 85.3 KByte (default)
------------------------------------------------------------
------------------------------------------------------------
Client connecting to 192.168.0.13, TCP port 5001
TCP window size: 85.0 KByte (default)
------------------------------------------------------------
[  5] local 192.168.0.10 port 55416 connected with 192.168.0.13 port 5001
[ ID] Interval       Transfer     Bandwidth
[  5]  0.0-10.2 sec  8.50 MBytes  7.01 Mbits/sec
[  4] local 192.168.0.10 port 5001 connected with 192.168.0.13 port 55140
[  4]  0.0-10.4 sec  16.4 MBytes  13.3 Mbits/sec

The throughput is not that great because the laptop is connected over WiFi only. The server is connected to the router using a 1Gbps ethernet cable.

iperf to the outside world works as advertised (ISP says 1.1Mbps UL / 31.5Mbps DL):

bicou@dikkenek:~$ iperf -c iperf.testdebit.info -r
------------------------------------------------------------
Server listening on TCP port 5001
TCP window size: 85.3 KByte (default)
------------------------------------------------------------
------------------------------------------------------------
Client connecting to iperf.testdebit.info, TCP port 5001
TCP window size: 85.0 KByte (default)
------------------------------------------------------------
[  3] local 192.168.0.10 port 37395 connected with 89.84.127.54 port 5001
[ ID] Interval       Transfer     Bandwidth
[  3]  0.0-11.0 sec  1.88 MBytes  1.43 Mbits/sec
[  5] local 192.168.0.10 port 5001 connected with 89.84.127.54 port 33129
[  5]  0.0-10.2 sec  30.4 MBytes  24.9 Mbits/sec

My main concern is http slowness, which is almost always 5.5 seconds late.

The server runs Debian 8 jessie, the laptop runs Mac OS X.10 Yosemite.

What tools can I use to troubleshoot the Debian slowness?

Edit: as Otheus pointed out, it's likely a DNS issue. Here's a test that confirms it:

bicou@dikkenek:~$ time curl -sIH 'Host: free.fr' 212.27.48.10
HTTP/1.1 302 Moved Temporarily
Server: nginx
Date: Mon, 11 May 2015 21:57:19 GMT
Content-Type: text/html
Content-Length: 154
Connection: keep-alive
Location: http://portail.free.fr/


real    0m0.034s
user    0m0.004s
sys     0m0.000s

Now how can I speed things up here?