Have you considered using some system where your character is rendered as individual component parts, body, head, feet, hands (6 parts?), and you have some kind of key framing, and transition frames between?
Paper doll technique gets rid of your problem, but it often looks kind of bad if you ask me. Especially when characters are turning.
If you are using frame by frame animation, it will propably soon become extremely tedious to draw all those in-betweens. When your character has more moves, like 10-15 different animations, it will get overwhelming, because the number of in-betweens would be the number of animations times itself. More transistions than animations, that is.
If your game doesn't have slo-mo effects or runs at an extremely low pace I wouldn't worry about it