There is no need to reboot regularly (unless you have a memory leak in Windows).

It could be a bad execution plan issue, with the execution plan flushed out of cache after the server is rebooted (and re-built when procedure is run). You could try DBCC FREEPROCCACHE (which will flush the execution plans).

The only way you will find out the cause for certain is to run profiler and perfmon, comparing against a benchmark.