But I got my starter replaced about 4 months ago. It was a new one so why is it not working?

There are other reasons for starting difficulty, including:
Compression loss
Failing ignition (spark plugs, plug wires, AND ignition coils, normal maintenance items every 30,000 miles)
Weak battery
Failing electrical grounds


Looks like you have some things to check on.

Can you use the N3Z1 starter for the 2005 rx8 or do you need to use the N3H1 A version?

If you can bang on your starter and then turn a car over, that is a definite sign that the starter is bad