Ssh connection freezes all the time

My brand new centos server has some trouble with openssh.
The shell freezes, sometimes after 10 seconds, sometimes after 2-3 minutes. (Connection closed by host)
When the shell freezes, I can't log in again for about 10 minutes.

I tried all the classic solutions like enabling the KeepAlive interval, disabling DNS, and disabling the GSSAPIAuthentication.

SELinux and iptables are disabled.

Last lines of my /var/log/secure:

Nov 17 04:33:07 tp sshd[2152]: Received disconnect from 194.190.136.163: 11: Bye Bye
Nov 17 04:33:07 tp sshd[2153]: pam_unix(sshd:auth): authentication failure; logname= uid=0 euid=0 tty=ssh ruser= rhost=194.190.136.163  user=root
Nov 17 04:33:09 tp sshd[2153]: Failed password for root from 194.190.136.163 port 48488 ssh2
Nov 17 04:33:09 tp sshd[2154]: Received disconnect from 194.190.136.163: 11: Bye Bye
Nov 17 04:33:10 tp sshd[2155]: pam_unix(sshd:auth): authentication failure; logname= uid=0 euid=0 tty=ssh ruser= rhost=194.190.136.163  user=root
Nov 17 04:33:12 tp sshd[2155]: Failed password for root from 194.190.136.163 port 48737 ssh2
Nov 17 10:35:37 tp sshd[2299]: Accepted password for root from 37.221.161.234 port 47783 ssh2
Nov 17 10:35:37 tp sshd[2299]: pam_unix(sshd:session): session opened for user root by (uid=0)

The debug after ssh -vvv:

OpenSSH_6.1p1, OpenSSL 1.0.0-fips 29 Mar 2010
debug1: Reading configuration data /etc/ssh/ssh_config
debug1: /etc/ssh/ssh_config line 51: Applying options for *
debug2: ssh_connect: needpriv 0
debug1: Connecting to ipserver [ipserver] port 22.
debug1: Connection established.
debug1: identity file /home/masufasu/.ssh/id_rsa type -1
debug1: identity file /home/masufasu/.ssh/id_rsa-cert type -1
debug1: identity file /home/masufasu/.ssh/id_dsa type -1
debug1: identity file /home/masufasu/.ssh/id_dsa-cert type -1
debug1: Remote protocol version 2.0, remote software version OpenSSH_5.3
debug1: match: OpenSSH_5.3 pat OpenSSH_5*
debug1: Enabling compatibility mode for protocol 2.0
debug1: Local version string SSH-2.0-OpenSSH_6.1
debug2: fd 3 setting O_NONBLOCK
debug3: load_hostkeys: loading entries for host "ipserver" from file "/home/masufasu/.ssh/known_hosts"
debug3: load_hostkeys: found key type RSA in file /home/masufasu/.ssh/known_hosts:5
debug3: load_hostkeys: loaded 1 keys
debug3: order_hostkeyalgs: prefer hostkeyalgs: ssh-rsa-cert-v01@openssh.com,ssh-rsa-cert-v00@openssh.com,ssh-rsa
debug1: SSH2_MSG_KEXINIT sent
debug1: SSH2_MSG_KEXINIT received
debug2: kex_parse_kexinit: diffie-hellman-group-exchange-sha256,diffie-hellman-group-exchange-sha1,diffie-hellman-group14-sha1,diffie-hellman-group1-sha1
debug2: kex_parse_kexinit: ssh-rsa-cert-v01@openssh.com,ssh-rsa-cert-v00@openssh.com,ssh-rsa,ssh-dss-cert-v01@openssh.com,ssh-dss-cert-v00@openssh.com,ssh-dss
debug2: kex_parse_kexinit: aes128-ctr,aes192-ctr,aes256-ctr,arcfour256,arcfour128,aes128-cbc,3des-cbc,blowfish-cbc,cast128-cbc,aes192-cbc,aes256-cbc,arcfour,rijndael-cbc@lysator.liu.se
debug2: kex_parse_kexinit: aes128-ctr,aes192-ctr,aes256-ctr,arcfour256,arcfour128,aes128-cbc,3des-cbc,blowfish-cbc,cast128-cbc,aes192-cbc,aes256-cbc,arcfour,rijndael-cbc@lysator.liu.se
debug2: kex_parse_kexinit: hmac-md5,hmac-sha1,umac-64@openssh.com,hmac-sha2-256,hmac-sha2-512,hmac-ripemd160,hmac-ripemd160@openssh.com,hmac-sha1-96,hmac-md5-96
debug2: kex_parse_kexinit: hmac-md5,hmac-sha1,umac-64@openssh.com,hmac-sha2-256,hmac-sha2-512,hmac-ripemd160,hmac-ripemd160@openssh.com,hmac-sha1-96,hmac-md5-96
debug2: kex_parse_kexinit: none,zlib@openssh.com,zlib
debug2: kex_parse_kexinit: none,zlib@openssh.com,zlib
debug2: kex_parse_kexinit: 
debug2: kex_parse_kexinit: 
debug2: kex_parse_kexinit: first_kex_follows 0 
debug2: kex_parse_kexinit: reserved 0 
debug2: kex_parse_kexinit: diffie-hellman-group-exchange-sha256,diffie-hellman-group-exchange-sha1,diffie-hellman-group14-sha1,diffie-hellman-group1-sha1
debug2: kex_parse_kexinit: ssh-rsa,ssh-dss
debug2: kex_parse_kexinit: aes128-ctr,aes192-ctr,aes256-ctr,arcfour256,arcfour128,aes128-cbc,3des-cbc,blowfish-cbc,cast128-cbc,aes192-cbc,aes256-cbc,arcfour,rijndael-cbc@lysator.liu.se
debug2: kex_parse_kexinit: aes128-ctr,aes192-ctr,aes256-ctr,arcfour256,arcfour128,aes128-cbc,3des-cbc,blowfish-cbc,cast128-cbc,aes192-cbc,aes256-cbc,arcfour,rijndael-cbc@lysator.liu.se
debug2: kex_parse_kexinit: hmac-md5,hmac-sha1,umac-64@openssh.com,hmac-ripemd160,hmac-ripemd160@openssh.com,hmac-sha1-96,hmac-md5-96
debug2: kex_parse_kexinit: hmac-md5,hmac-sha1,umac-64@openssh.com,hmac-ripemd160,hmac-ripemd160@openssh.com,hmac-sha1-96,hmac-md5-96
debug2: kex_parse_kexinit: none,zlib@openssh.com
debug2: kex_parse_kexinit: none,zlib@openssh.com
debug2: kex_parse_kexinit: 
debug2: kex_parse_kexinit: 
debug2: kex_parse_kexinit: first_kex_follows 0 
debug2: kex_parse_kexinit: reserved 0 
debug2: mac_setup: found hmac-md5
debug1: kex: server->client aes128-ctr hmac-md5 none
debug2: mac_setup: found hmac-md5
debug1: kex: client->server aes128-ctr hmac-md5 none
debug1: SSH2_MSG_KEX_DH_GEX_REQUEST(1024<1024<8192) sent
debug1: expecting SSH2_MSG_KEX_DH_GEX_GROUP
debug2: dh_gen_key: priv key bits set: 128/256
debug2: bits set: 473/1024
debug1: SSH2_MSG_KEX_DH_GEX_INIT sent
debug1: expecting SSH2_MSG_KEX_DH_GEX_REPLY
debug1: Server host key: RSA cf:f9:ec:46:7d:61:78:ec:ff:b3:c4:a6:1f:42:f0:ea
debug3: load_hostkeys: loading entries for host "ipserver" from file "/home/masufasu/.ssh/known_hosts"
debug3: load_hostkeys: found key type RSA in file /home/masufasu/.ssh/known_hosts:5
debug3: load_hostkeys: loaded 1 keys
debug1: Host 'ipserver' is known and matches the RSA host key.
debug1: Found key in /home/masufasu/.ssh/known_hosts:5
debug2: bits set: 495/1024
debug1: ssh_rsa_verify: signature correct
debug2: kex_derive_keys
debug2: set_newkeys: mode 1
debug1: SSH2_MSG_NEWKEYS sent
debug1: expecting SSH2_MSG_NEWKEYS
debug2: set_newkeys: mode 0
debug1: SSH2_MSG_NEWKEYS received
debug1: Roaming not allowed by server
debug1: SSH2_MSG_SERVICE_REQUEST sent
debug2: service_accept: ssh-userauth
debug1: SSH2_MSG_SERVICE_ACCEPT received
debug2: key: /home/masufasu/.ssh/id_rsa ((nil))
debug2: key: /home/masufasu/.ssh/id_dsa ((nil))
debug1: Authentications that can continue: publickey,password
debug3: start over, passed a different list publickey,password
debug3: preferred publickey,keyboard-interactive,password
debug3: authmethod_lookup publickey
debug3: remaining preferred: keyboard-interactive,password
debug3: authmethod_is_enabled publickey
debug1: Next authentication method: publickey
debug1: Trying private key: /home/masufasu/.ssh/id_rsa
debug3: no such identity: /home/masufasu/.ssh/id_rsa
debug1: Trying private key: /home/masufasu/.ssh/id_dsa
debug3: no such identity: /home/masufasu/.ssh/id_dsa
debug2: we did not send a packet, disable method
debug3: authmethod_lookup password
debug3: remaining preferred: ,password
debug3: authmethod_is_enabled password
debug1: Next authentication method: password
debug3: packet_send2: adding 64 (len 60 padlen 4 extra_pad 64)
debug2: we sent a password packet, wait for reply
debug1: Authentication succeeded (password).
Authenticated to ipserver ([ipserver]:22).
debug2: fd 5 setting O_NONBLOCK
debug3: fd 6 is O_NONBLOCK
debug1: channel 0: new [client-session]
debug3: ssh_session2_open: channel_new: 0
debug2: channel 0: send open
debug1: Requesting no-more-sessions@openssh.com
debug1: Entering interactive session.
debug2: callback start
debug2: fd 3 setting TCP_NODELAY
debug3: packet_set_tos: set IP_TOS 0x10
debug2: client_session2_setup: id 0
debug2: channel 0: request pty-req confirm 1
debug1: Sending environment.
debug3: Ignored env XDG_VTNR
debug3: Ignored env XDG_SESSION_ID
debug3: Ignored env HOSTNAME
debug3: Ignored env IMSETTINGS_INTEGRATE_DESKTOP
debug3: Ignored env GPG_AGENT_INFO
debug3: Ignored env TERM
debug3: Ignored env SHELL
debug3: Ignored env XDG_MENU_PREFIX
debug3: Ignored env HISTSIZE
debug3: Ignored env XDG_SESSION_COOKIE
debug3: Ignored env GJS_DEBUG_OUTPUT
debug3: Ignored env WINDOWID
debug3: Ignored env GNOME_KEYRING_CONTROL
debug3: Ignored env QTDIR
debug3: Ignored env QTINC
debug3: Ignored env GJS_DEBUG_TOPICS
debug3: Ignored env IMSETTINGS_MODULE
debug3: Ignored env QT_GRAPHICSSYSTEM_CHECKED
debug3: Ignored env USER
debug3: Ignored env LS_COLORS
debug3: Ignored env SSH_AUTH_SOCK
debug3: Ignored env SESSION_MANAGER
debug3: Ignored env USERNAME
debug3: Ignored env PATH
debug3: Ignored env MAIL
debug3: Ignored env DESKTOP_SESSION
debug3: Ignored env QT_IM_MODULE
debug3: Ignored env PWD
debug1: Sending env XMODIFIERS = @im=ibus
debug2: channel 0: request env confirm 0
debug3: Ignored env GNOME_KEYRING_PID
debug1: Sending env LANG = it_IT.UTF-8
debug2: channel 0: request env confirm 0
debug3: Ignored env KDE_IS_PRELINKED
debug3: Ignored env KDEDIRS
debug3: Ignored env AUTOJUMP_DATA_DIR
debug3: Ignored env GDMSESSION
debug3: Ignored env HISTCONTROL
debug3: Ignored env KRB5CCNAME
debug3: Ignored env XDG_SEAT
debug3: Ignored env HOME
debug3: Ignored env SHLVL
debug3: Ignored env GNOME_DESKTOP_SESSION_ID
debug3: Ignored env AUTOJUMP_HOME
debug3: Ignored env LOGNAME
debug3: Ignored env QTLIB
debug3: Ignored env DBUS_SESSION_BUS_ADDRESS
debug3: Ignored env LESSOPEN
debug3: Ignored env PROMPT_COMMAND
debug3: Ignored env WINDOWPATH
debug3: Ignored env XDG_RUNTIME_DIR
debug3: Ignored env DISPLAY
debug3: Ignored env QT_PLUGIN_PATH
debug3: Ignored env COLORTERM
debug3: Ignored env XAUTHORITY
debug3: Ignored env _
debug2: channel 0: request shell confirm 1
debug2: callback done
debug2: channel 0: open confirm rwindow 0 rmax 32768
debug2: channel_input_status_confirm: type 99 id 0
debug2: PTY allocation request accepted on channel 0
debug2: channel 0: rcvd adjust 2097152
debug2: channel_input_status_confirm: type 99 id 0
debug2: shell request accepted on channel 0
Last login: Sat Nov 16 18:38:52 2013 from 2.237.239.68

]0;root@tp:~[?1034h[root@tp ~]# debug1: client_input_channel_req: channel 0 rtype keepalive@openssh.com reply 1
debug1: client_input_channel_req: channel 0 rtype keepalive@openssh.com reply 1
debug1: client_input_channel_req: channel 0 rtype keepalive@openssh.com reply 1
debug1: client_input_channel_req: channel 0 rtype keepalive@openssh.com reply 1
debug1: client_input_channel_req: channel 0 rtype keepalive@openssh.com reply 1
debug1: client_input_channel_req: channel 0 rtype keepalive@openssh.com reply 1
debug1: client_input_channel_req: channel 0 rtype keepalive@openssh.com reply 1
debug1: client_input_channel_req: channel 0 rtype keepalive@openssh.com reply 1
debug1: client_input_channel_req: channel 0 rtype keepalive@openssh.com reply 1
debug1: client_input_channel_req: channel 0 rtype keepalive@openssh.com reply 1
debug1: client_input_channel_req: channel 0 rtype keepalive@openssh.com reply 1
debug1: client_input_channel_req: channel 0 rtype keepalive@openssh.com reply 1
debug1: client_input_channel_req: channel 0 rtype keepalive@openssh.com reply 1
debug1: client_input_channel_req: channel 0 rtype keepalive@openssh.com reply 1
debug1: client_input_channel_req: channel 0 rtype keepalive@openssh.com reply 1
debug1: client_input_channel_req: channel 0 rtype keepalive@openssh.com reply 1
debug1: client_input_channel_req: channel 0 rtype keepalive@openssh.com reply 1
debug1: client_input_channel_req: channel 0 rtype keepalive@openssh.com reply 1
debug1: client_input_channel_req: channel 0 rtype keepalive@openssh.com reply 1
debug1: client_input_channel_req: channel 0 rtype keepalive@openssh.com reply 1
debug1: channel 0: free: client-session, nchannels 1
debug3: channel 0: status: The following connections are open:
  #0 client-session (t4 r0 i0/0 o0/0 fd 4/5 cc -1)

debug1: fd 1 clearing O_NONBLOCK
debug3: fd 2 is not O_NONBLOCK
Connection to ipserver closed by remote host.
Connection to ipserver closed.
Transferred: sent 2312, received 2952 bytes, in 211.2 seconds
Bytes per second: sent 10.9, received 14.0
debug1: Exit status -1

netstat -lnpt | grep 22:

tcp        0      0 0.0.0.0:22                  0.0.0.0:*                   LISTEN      1495/sshd           
tcp        0      0 :::22                       :::*                        LISTEN      1495/sshd   

/var/log/messages

nf_conntrack version 0.5.0 (16384 buckets, 65536 max)
r8169 0000:02:00.0: firmware: requesting rtl_nic/rtl8168e-3.fw
r8169 0000:02:00.0: eth0: link down
r8169 0000:02:00.0: eth0: link down
ADDRCONF(NETDEV_UP): eth0: link is not ready
r8169 0000:02:00.0: eth0: link up
ADDRCONF(NETDEV_CHANGE): eth0: link becomes ready