My ssh connection to my server works every 30 min for around 10 min.
Things that I figure out that might be the problem:
The server is underload (it is a database server), but on those spare moments that I can connect, it is still under the same load, which doesnt make sense.
The server is a ubuntu, and the consolekit was using a lot of virtual memory. Restarted the consolekit and it seems to be using a right amount of memory now.
It is not the host alows or deny. Those are setup properly.
It is not a firewall problem. Those settings were working and the same settings are working for other similar machines.
It is on the ec2. Amazon cloud.