It should not be slow on a dedicated server.
I run FB with sh404SEF on my site and the average page load time (if you have fast internet access) is 500-700ms
I had up to 200 concurrent users so far, which got the server to 25% busy.
I have about 25-30k unique visitors per month now doing 250k pageviews per month. No performance issues whatsoever.
I also have a much larger category structure that creates extra workload.
Check it out:
www.starVmax.com
First off:
Check you error log. You must not see tons of errors and warnings. It puts a huge burden on apache.
What other mambots and plugins are you running?
Also Joomla 1.5 is slower than 1.0.15 (which I am running).