Coloring multiple sprites

I have a sprite sheet that builds the character with multiple sprites all packed together (see image). This is only a very small portion of the sprite sheet, but it allows the user to change hair styles, shirts, pants, and accessory items with any color they choose. So I may end up with a hundred different hair styles and accessories that they player can choose from. In my drawing method, I simply draw everything in order (first the body, then the shirt, then the pants, then the hair, etc), each with their respective colors. This has been working great, but now I am presented with another challenge: I want to create character sprites where the character pushes, pulls, climbs, jumps, etc. Now all of a sudden my sprite sheet will get exponentially bigger because I have to create at least 4 times the number sprites. This will create a large png, much bigger than I want people on the phone to have to store.

So my question is, can a shader be used to to duplicate this process somehow with much smaller file sizes? If so, I am very new to shaders and would ask for a demo on how I could accomplish this. Otherwise, are there other suggestions? Also, I am currently using MonoGame.Extended to draw the textures. Thanks in advance.

The filesize here really isn’t a problem.
Just think of 3D Games with HD-Textures and smartphones these days can still run them.
So when going for a low-res pixelart-style you could have hundreds of sprites in a single file without noticing too much of an impact.
But if you are still looking for a more memory-savy method you could use an animation-software like Spine2D. But style-wise it will differ.