В нашей локальной сети DNS-сервер не возвращал обратную запись DNS для своего собственного IP-адреса. Это замедлило первый прыжок трассера (с задержкой около 17-25 секунд).
BloodPhilia предложила попробовать DNS-сервер Google, который имел обратную запись DNS для своего IP.
Проблема была решена удалением адаптера IPv6 (ранее он был только отключен).