Yes, rotoscoping is time-consuming. Check out the options ($) by Imagineer systems: Mocha etc.
Within AE, the idea is to study the motion, then create a key for the mask shape when the shape-changing changes direction, or is at a point of inflection. For example, if something gets bigger, then smaller, add a key when it stops growing and starts shrinking. Let AE do the interpolation between. Don’t set keys at a regular interval unless the motion specifically requires it.
Also, separate a complex shape into its non-changing elements, if you can. If the thing has five elements that change position, that’s easier: you just move the masks, rather than having to aniamte the shape of one.
Of course, if the shape is organic, like a flowing cape, you probably have to do that frame-by-frame. Try switching rotobezier on for that one.
Note that when rotating a mask, AE makes the mask vertices travel in a straight line between keys.