Yum seems a little faster than apt-get/aptitude to me. Do you have the yum cache enabled? Yum normally downloads its package lists for every command, but you can make it cache the package list like apt-get does.