You could try adding that index but often the suggestions for missing indexes are actually worse. I have very often seen that adding the suggested indexes actually slows down the query.

There could be any number of things that are causing it slow down now when it didn't in the past. Stale statistics, parameter sniffing, fragmented indexes, etc etc etc....

If you could post the actual execution plan we can take a look and see what is going on there.