How to debug sporadic outbound connection timeouts?

I'm having trouble connecting to my remote host via SSH. I have narrowed the issue down to my local host only as other clients make nominal (fast and stable) connections every time.

Attempting to connect to remotehost.example.net from localhost via SSH will time out all but about 1 out of 10 attempts (it hangs here and then times out):

515 chris@localhost ~ $ ssh -vvv remotehost-root
OpenSSH_6.4, OpenSSL 1.0.1e 11 Feb 2013
debug1: Reading configuration data /home/chris/.ssh/config
debug1: /home/chris/.ssh/config line 43: Applying options for remotehost-root
debug1: Reading configuration data /etc/ssh/ssh_config
debug2: ssh_connect: needpriv 0
debug1: Connecting to remotehost.example.net [123.123.123.123] port 12345.
^C

localhost is an up-to-date Arch system:

517 chris@localhost ~ $ uname -a
Linux localhost 3.12.1-1-ARCH #1 SMP PREEMPT Thu Nov 21 08:18:42 CET 2013 x86_64 GNU/Linux

And I'm using an SSH config file to alias remotehost as follows:

521 chris@localhost .ssh $ cat ~/.ssh/config
...
host remotehost-root
  HostName remotehost.example.net
  User root
  Port 12345
  IdentityFile ~/.ssh/remotehost-root.id_rsa
...

This is a recent problem, but unfortunately I don't recall making changes to anything relevant. I'm not sure what to check.

Maybe it's worth noting that this affects all SSH connections (such as git over ssh and SFTP) and not just the command line SSH tool.

I don't have any trouble accessing remotehost.example.net over any other protocol (e.g. HTTP, HTTPS, BitTorrent, etc).

The only active/uncommented line in /etc/ssh/ssh_config is:

ServerAliveInterval 120

Where else can I look? What other debug tools can I use (all I can think to do is run ssh -vvv)?

I tried running tcpdump on remotehost while attempting a connection, but couldn't figure out how to filter the packets from the shell running tcpdump thus infinite-loop spamming myself out of any useful diagnostics.

UPDATE 1: Worth noting that I've been able to duplicate this behavior on a second SSH host, as well as an IRC server, thus proving (in my mind) that this is an issue wholly within some config on my local host.

UPDATE 2: Also worth noting that while my localhost has trouble with these outbound connections, other clients (including on one, and one off, my LAN) have no issues whatsoever to any of the same remote hosts, or any other hosts. Again, leading me to believe that this is solely some config issue within localhost (but maybe I'm wrong?).

UPDATE 3: I have removed the openssh package (and configs) from localhost and reinstalled, to no avail.

A timeout could happen if you have a high cpu load on your local machine, i had that issue sometimes a few years ago. My Backup process back then did eat my IO + cpu.

As the server i connected to was GPRS and therefor slow by design i did not immediately think of the local host as a problem.

Additionally you might as you said have a limit of connections you are able to use to.

personally i would check the packets with something like wireshark.

1) Do you have GSSAPIAuthentication enabled? Try setting that to "no" in /etc/ssh/sshd_config

2) Have you checked if this is a DNS lookup issue? Try adding the destination host and its ip address to /etc/hosts and retry your ssh connect

3) To do your tcpdump, you can use the following:

tcpdump -n "port 22 and dst <ip address of destination host>"

4) Can you post the full output of the -vvv debug? Or was that it? Can you show what it says after the timeout?

On any occasion where it hangs, you can also simply do netstat -an | grep <ip of remote host> and if the "State" field is "SYN_SENT" then you know it's being blocked on some level.