Technically speaking, anything can work.
Personally, I've just always used Photoshop and Aseprite. It ultimately doesn't really matter, as the learning curve is going to spike you hard, irrespective of whichever program you decide to use.
I'd say Aseprite is probably the best if you're looking for free/cheap programs that has the basic functions that you'll need for a game; you can compile it for free, iirc. But even if you have to drop the money, it's not particularly expensive on Steam.
Tl;dr: It doesn't really matter, pick 1 and practice so you can produce quality work in whichever program you're using.