5-10 sekunden ist für die Anzahl der Einträge auf jeden Fall zu lang. was sagt dir den EXPLAIN?
http://dev.mysql.com/doc/refman/5.1/de/explain.htm...