Indeed PNG format is a good choice, it provides better lossless compression compared with RLE, and also you can define alpha channel.
Two techniques that I follow when I'm dealing with sprites is to use eg RGB(0,0,0) to identify "void space" and make black equal to eg RGB(1,1,1) or use 2 separate images files, one for content and another for alpha channel and compine them at runtime or even use them to "prebuild" a custom img format. (actually I've done this once and I'm reusing the same code). Both techniques are not perfect (especially the 2nd is slow in runtime compine), but eliminate the need of an image processing tool that is alpha-channel aware, at least for my needs.