Make a simple test. Take stored procedure which is running slow after reboot of the server (or RESTORE) and execute quickly from the second execution onwards.

Simply recompile that stored procedure and see if you are having more time or less?

Let us see know the outcome.