First ssh connection takes several minutes

I’m running on Ubuntu 17.04, openssh-client==7.4p1-10. I’m having problems with executing ssh commands, like:

rsync -t -e ssh -p 22 script.sh root@remote.server:/var/lib/script.sh
_ ssh -p 22 -l root root@remote.server rsync --server -te.LsfxC . /var/lib/script.sh

it takes rsync 6 minutes to sync that script which has 4kB. The problem isn’t just with rsync also git push over ssh sometimes gets sucked.

Funny thing is that after interrupting the process and executing it again it works immediately:

^Crsync error: unexplained error (code 130) at rsync.c(638) [sender=3.1.2]
rsync: [sender] write error: Broken pipe (32)

It doesn’t seem to be a DNS issue, I’ve already disabled GSSAPI:

/etc/ssh/ssh_config:

   GSSAPIAuthentication no
   GSSAPIDelegateCredentials no

without any effect, I’ve tried forcing IPv4 connection with-4` also without any success. Any idea what could be wrong?

Here’s strace of that process:

strace: Process 7610 attached
select(8, [3 5], [], NULL, NULL)        = 1 (in [3])
clock_gettime(CLOCK_BOOTTIME, {42870, 893598449}) = 0
read(3, "372oyu331J20327264325357274vn233nG207207c251230341NzUk261351v23353"..., 8192) = 44
clock_gettime(CLOCK_BOOTTIME, {42870, 894108136}) = 0
clock_gettime(CLOCK_BOOTTIME, {42870, 894258960}) = 0
select(8, [3 5], [6], NULL, NULL)       = 1 (out [6])
clock_gettime(CLOCK_BOOTTIME, {42870, 894325845}) = 0
write(6, "37", 7)           = 7
clock_gettime(CLOCK_BOOTTIME, {42870, 894439661}) = 0
clock_gettime(CLOCK_BOOTTIME, {42870, 894473071}) = 0
select(8, [3 5], [], NULL, NULL)        = 1 (in [5])
clock_gettime(CLOCK_BOOTTIME, {42870, 894558087}) = 0
read(5, "2717", 16384) = 11
clock_gettime(CLOCK_BOOTTIME, {42870, 894661575}) = 0
clock_gettime(CLOCK_BOOTTIME, {42870, 894699595}) = 0
select(8, [3 5], [3], NULL, NULL)       = 1 (out [3])
clock_gettime(CLOCK_BOOTTIME, {42870, 894780961}) = 0
write(3, "f166UF|B1315nYP355f|177|234v371322236*)32`3214225$u337"..., 52) = 52
clock_gettime(CLOCK_BOOTTIME, {42870, 894852781}) = 0
clock_gettime(CLOCK_BOOTTIME, {42870, 894874370}) = 0
select(8, [3 5], [], NULL, NULL)        = 1 (in [3])
clock_gettime(CLOCK_BOOTTIME, {42870, 923152465}) = 0
read(3, "3103258332212)re262322^f275324X{36123f211mk'213224v204322n25221"..., 8192) = 44
clock_gettime(CLOCK_BOOTTIME, {42870, 923618233}) = 0
clock_gettime(CLOCK_BOOTTIME, {42870, 923845130}) = 0
select(8, [3 5], [6], NULL, NULL)       = 1 (out [6])
clock_gettime(CLOCK_BOOTTIME, {42870, 923946992}) = 0
write(6, "17", 5)               = 5
clock_gettime(CLOCK_BOOTTIME, {42870, 924002335}) = 0
clock_gettime(CLOCK_BOOTTIME, {42870, 924027449}) = 0
select(8, [3 5], [], NULL, NULL)        = 1 (in [3])
clock_gettime(CLOCK_BOOTTIME, {42870, 943180384}) = 0
read(3, "326U3220246374201K246177!z265302^252371255215355265356313322W2341`%21520P"..., 8192) = 176
close(6)                                = 0
close(5)                                = 0
clock_gettime(CLOCK_BOOTTIME, {42870, 943307191}) = 0
clock_gettime(CLOCK_BOOTTIME, {42870, 943334146}) = 0
close(7)                                = 0
select(8, [3], [3], NULL, NULL)         = 1 (out [3])
clock_gettime(CLOCK_BOOTTIME, {42870, 943414987}) = 0
write(3, "023627233p303324302222mD242Y_34S365366p214z320367.sN252337322S202("..., 36) = 36
rt_sigaction(SIGWINCH, NULL, {0x5639600b7460, [], SA_RESTORER, 0x7f7046de37f0}, 8) = 0
rt_sigaction(SIGWINCH, {SIG_DFL, [], SA_RESTORER, 0x7f7046de37f0}, NULL, 8) = 0
write(3, "F226207724320733316371U$326Y314253310p210354240247322n32272A312312:252324"..., 60) = 60
ioctl(0, TCGETS, 0x7ffc20de6720)        = -1 ENOTTY (Inappropriate ioctl for device)
fcntl(0, F_GETFL)                       = 0x802 (flags O_RDWR|O_NONBLOCK)
fcntl(0, F_SETFL, O_RDWR)               = 0
ioctl(1, TCGETS, 0x7ffc20de6720)        = -1 ENOTTY (Inappropriate ioctl for device)
fcntl(1, F_GETFL)                       = 0x802 (flags O_RDWR|O_NONBLOCK)
fcntl(1, F_SETFL, O_RDWR)               = 0
ioctl(2, TCGETS, {B38400 opost isig icanon echo ...}) = 0
shutdown(3, SHUT_RDWR)                  = 0
close(3)                                = 0
exit_group(0)                           = ?
+++ exited with 0 +++