Well, the best way to count the number of rows in a table is to use a fast full-index scan. To do that, use the index_ffs(table,index) hint.
Testing this out on one of our own development tables with approximately 5 million rows, I tried this first:
That took 25 seconds. Then I tried this:
/*+ index_ffs(f,sys_c0012345) */ count(*)
FROM foo f
That reduced it to 5 seconds. Nice, eh? Supposedly you can improve this even further by using the parallel _index hint as well, but it didn't seem to help in my tests, though I suspect that's due to the way our database is setup.
On a side note, be sure to give your indexes and primary keys meaningful names, so you don't have to refer back to them using Oracle's default "sys_xxxx" naming convention, which is both ugly and not as clear.