Slow Queries

I have a stored procedure that is taking forever to run during our month end processing. It takes about 18 hours to run. I basically creates a cursor for approximately 1.6 million records. Then it loops through these records and checks if the ‘id’ exists in another table, which contains about 4.6 million records. If the ‘id’ doesn’t exist and some other criteria exists, a record gets created in the 2nd table. I’ve already added keys to the appropriate tables as they previously didn’t have any. That seemed to only speed it up by about 6 hours. Does anyone have any other ideas or things I should look for to make this more efficient? Thanks!