Yes, a new CPU is the only thing will help, although transcoding times like those usually mean that you are over-compressing the movie. You really should stay above 75%. If you're watching on a smaller screen, you could turn off the quality settings and just use deep-analysis. That would speed it up.
2 things will make it go faster, CPU-wise. More L-2 cache will hugely speed up the analysis phase (1 MB), and more speed. You can get a 939 X2 CPU for next to nothing these days, any one of them will be a big help over what you have now. With 1 MB L-2 cache x 2 and 2 cores, you'll be impressed.Shrink is multi-threaded, so dual core really helps.
More RAM will not help, but faster RAM will help. Either higher clock speed or tighter timings. The benefit there will be small.