If nothing changed, then it wouldn't be taking 6 times as long to run. Therefore, something must have changed. It might not be the data in the tables, but there's probably something.

Start by looking at the procedure and examine the execution plans. They'll tell you where your problems lie.

Take the information from there and check your existing indexes. Create new ones where appropriate, but don't believe everything that SQL Server tells you is missing; make sure they make sense and that you don't create duplicates. Overindexing is a real danger you need to avoid.

If you need more information on execution plans, check out Grant Fritchey's book on them. It is very good.

For more information on indexing, this site has an excellent stairway on the topic: http://www.sqlservercentral.com/stairway/72399/

Tuning is both an art and a science. Many people in this world spend a lot of time doing it and there's a lot to consider. You'll probably come up with the phrase "it depends" a lot. There's also most likely more than one way to fix the problem, but first you have to identify the problem. Don't underestimate the value of trying different approaches on a test server and benchmarking to see your results.