Если совсем кратко, то процесс согласования ключа с удаленной стороной проваливается иногда почему-то.
Так бывает, чаще всего из-за потери или порчи пакетов.
У вас на линии связи происходит порча пакетов. Разберитесь с ней.
Раньше не было таких записей только потому, что это "замалчивалось". Теперь вы их видите, можете оценить количество и что-то предпринять.
Посмотрите на D.12-8, немного полегче должно стать. Но вообще у вас сильные потери между клиентом и сервером, потому все равно это потенциально проблемно.