Ok then you have to work on DB & tables optimization (index/reindex).
Simple count cannot be bottleneck.
Anyway if you choose to remove these from header, I recommend you to go into core and change header hook - so no function get hooked into header.