Fine mesh sieve is the usual way, but the way you describe it, yours is not fine enough.
Look in professional stores for a "chinois", this is the kind of sieve you need. But yes, it will take a long time.
In classic restaurants, the stock will be cleared before going through the chinois. This is done by floating a rack of eggwhite which bounds the stray proteins. It is at least as slow as the cheesecloth, but more nerve wracking, because you have to do it manually, and it is rather finicky and can easily go wrong.
I remember reading about a modern trick of clearing which used gelatine and freezing the stock without a mesh or a rack, but don't know any more what it was. Maybe somebody else has read it and can supply the details.
Edit I returned home and looked the freezing method up; it is listed in the book "Cooking for geeks". It contains the sentence
As the water in the stock freezes, it will push the impurities into the gelatin
The book also has pictures. They show that you don't end up with fine protein sediment clogging your sieve and finest slit in the stock. The first picture shows the drip-freeze filtered stock compared to the same stock filtered at 100 microns, the difference is large. The second picture shows that after the procedure, what stays in the sieve are cohesive pieces of gelatine with the particles trapped inside, not a film of the scum. So it seems that there is a reason for freezing first.
You can also skip the need of clearing if you never bring your stock to a boil, but keep it at a bare simmer. This is quite easy with modern programmable cookers, if they have a dedicated soup or stock mode, but will require a lot of baby sitting on a stovetop.
For home use, I just don't bother clearing my stock, I just use a tea sieve to remove the worst of the protein. When simmered without allowing it to boil, this produces reasonably good stock without all the fuss.