I recently switched over to storing all my sprites as simple spans of paletted byte data. To call it RLE is over-indulging it, as it really is just a repeat count and then the bytes to copy, then a skip count. There are as many codes as needed for each line, and that's it.
It's pretty crap compression scheme, but it decompresses like lightening and I'm gonna spare a bit in the control byte to indicate a repeat count which will speed it up loads (a value of 0 on the repeat being then taken as a skip).
The net effect of this was to speed up transparent printing by loads as there are now no 'ifs' in the inner loop and it's pretty cache friendly. It also more than halved my data size.
Give it a whirl.....
