The two key questions are a) what is the size of your case - this will determine whether you can support a full size or only a half size card, and b) whether your motherboard supports PCI Express. It's 99% certain that it will do, in which case you have a very broad choice.
If my research is correct, though, it looks as if the HD5600 is a pretty capable graphics card, and you'd be looking at a fair bit of money to improve it. If I were you, I'd try the new game with your existing card and see how you get on before laying out money on another one.
I see that the recommended (as opposed to minimum) card for the game is an NVIDIA GeForce 260 or ATI Radeon HD 4870 or better: do some research on those, and then start looking at more expensive ones if you must... :-)