No, querying counting public entries in each category would be extremely db intensive. It just would scale well.
My thought is since I just added full support for entry meta which is to support custom fields; this could be extended to support taxonomy (category) meta. If I do that, then when an entry is added/updated the count for the categories could be calculated and saved in this meta. Doing this would allow me to have the grunt work done only when adding/updating an entry then pull this data based on user permissions to show the correct count. This still could mean an extra db request for each category be displayed instead of just the one presently, but those queries would at least be really quick to execute.