The fastest way to get a count of a table is exactly what you did. There are no tricks you can do that Oracle doesn't already know about.
There are somethings you have not told us. Namely why do you think think this should be faster?
For example:
I'll admit I wouldn't be happy with 41 seconds but really WHY do you think it should be faster? If you tell us the table has 18 billion rows and is running on the laptop you bought from a garage sale in 2001, 41 seconds is probably not that far outside "good as it will get" unless you get better hardware. However if you say you are on Oracle 9 and you ran statistics last summer well you'll probably get a different suggestions.