Unless you are dealing with a really complicated skin and/or have a lot of modules on each page, you may have another problem. I have a site with over 200K users and thousands of pages. We did add some additional indexes and are very strict about how new modules are developed, but I've never seen a skin be the cause of a performance issue (granted my skins are simple). Before presuming the skinning engine is the problem, you may want to mke sure your dnn site is fully optimized.
I haven't used this personally, but this module on snowcovered, advertises to tune up your database. There is also an Enterprise version with source. For $15, this may be worth checking out.
I think everyone will agree, a dnn site will never be as fast as an all static site, but done properly, I don't think dnn skins cost much more than master page themes.
I have noticed, if you have a site with a lot of pages and you put a lot of modules on a single page and you have a lot of roles you will take a performance hit. The page is just having to figure out a lot. Again, though, this has nothing to do with the skin.