Перефразируя известный анекдот:
- Бытует мнение что NAT на FreeBSD работает лучше и быстрее чем в Linux.
- Чем быстрее?
- Чем в Linux.

В качестве маршрутизатора серъёзен и Linux и FreeBSD и много других систем, а скорость обработки данных (будь то преобразование адресов или ещё что) зависит не столько от ОС, сколько от железа и, главным образом, от администратора и его начальника.

У вас какие критерии для выбора маршрутизатора?

А с самого сервера при этом как коннектится, быстро?
А какие процессы как память используют?
Сильно ли swap используется?
Как процессор нагружен на шлюзе?
И влияет ли на скорость количество пользователей - может с одним всё летает?
И вообще надо смотреть vmstat, iostat и т.п.

И вообще вы представляете себе что такое NAT ? какие ресурсы требуются для выполнения трансляции адресов ?

И ещё, там смотрели: http://www.usergate.ru/support/forum/

Да, частенько бывает, что проблемы подобного характера кроются в глючных картах, свитчах, на коленке собранных патч-кордах и аплинках.