PCI and PCI-Express are different connectors. From that, it looks like your motherboard uses AGP.
You's be lucky to find a graphics card that supports AGP these days, as it was discontinued over 8 years ago.
I have to say it probably isn't worth spending any money on a PC that is 15 years old, since the integrated graphics in a modern Celeron or AMD APU would perform better. You would be far better off to put the thing to bed and get yourself a cheap new machine.
The reason Linux gives lower FPS is probably because you're trying to run a 13 year old GPU on a (presumably) modern OS. Those cards are no longer supported by AMD, and Linux is probably using the generic driver for them, which will give bad performance.
You could try re-installing Windows XP, and seeing if you can find the last supported driver for the 9600, but there's really no upgrade path for you - there hasn't been for around 8-10 years...
Sorry there isn't better news, but that PC has had an incredibly long life, and is now pretty much beyont the point of being viable.