[PvK]

Few mages are stealthy. Also, Champion's Skull will get you one star, and eventually two, but is quite slow to try to get three or more stars with, since the requirement gets steeper rapidly, and the skull only gives a little experience each turn/month.

Another idea is to have the stealth level go up by +1 on a rare chance per turn spent sneaking - a chance that's inversely proportional to stealth skill. That would de-couple stealth skill from combat skill.

PvK