Try these:

1. If you don't have index, create it and make sure it does use the index you created.

2. Try to use "COUNT(ROWID)" instead of "COUNT(*)".

3. If the table is very huge, try to spread it acrossing multiple disks.

4. If it's not good enough, try parallel query.