First things first, look at the execution plan. See where it's hanging.

If you don't see anything there, check for blocks while it executes.

If that also looks fine, check CPU/IO usage and see if those are spiking for some reason on the box.

If not, make sure the proc hasn't actually changed (compare to source control versions).

If it hasn't, you can look into indexes/statistics/fragmentation on the tables it's pulling from. The only reason this isn't higher is because fragmentation usually doesn't happen out of the blue unless you have a huge data job on the tables..which I'm sure you would know about.