В процессе выяснения деталей в комментариях к вопросу было найдено решение.
В данном случае синхронизация выполнялась без использования опции `--times`, которая сохраняет время модификации файла при синхронизации. При этом не была использована опция `--size-only`, благодаря которой файлы с одинаковыми размерами считаются одинаковыми вне зависимости от времени изменения.
И получается, что даты изменения у всех уже синхронизированных файлов отличаются, и rsync при повторном запуске считает эти файлы потенциально разными и считает их контрольные суммы, чтобы сравнить их по содержимому. На это и уходило время.
Добавление опции `--size-only` существенно сократило время анализа файлов перед началом передачи.
Хотя, на мой взгляд лучше вместо этого по умолчанию всегда использовать `--times` (в том числе в составе `-a`), если возможно.
Кроме того, была использована опция `-v`, которая выводит информацию о синхронизируемых файлах, что тоже могло замедлять процесс, хотя, скорее всего ,не значительно.