> Убери кашпировского из цепочки и сравни время.
> Тогда будет более понятно кто виноват.

Закоментил строку smtpd_milters = unix:/klms/klms_milter_sock
Время отправки без изменений.
По ощущениям какой-то медленный алгоритм приёма письма от клиента. Будто где-то надо указать другой совместимый протокол.

В порядке фантазий - разработчик по умолчанию включает в инсталляционном пакете предельно совместимый древний протокол обмена, и есть более современный, но несовместимый с каким-нибудь нетскейпом или типа того, но адекватно работающий с современными почтовыми клиентами. Надо только вписать опцию в конфиг...