I am also struggling with this at the moment. Having a hard time understanding what to do here.
PNG24 and I think MS Paint don't handle transparency (unless MS Paint is doing something different these days). I don't have MS Paint on linux and I'm using Krita, but I tried saving the image without an alpha channel to see if that would work and it just resulted in having no transparency at all (so it exported with a background and everything). I tried setting the transparent pixels to both white and black and neither seemed to work. Fiddling with all my export options and no dice.
Just tried applying a light blur to the sprite and that seemed to help without being too noticeable on this particular image at least. But if I could do something while keeping my sprites sharp that would be ideal.