It sounds to me that you need to get deeper in the running sql code and not playing with the indexes, 30 minutes for a batch it sounds me as a bad developed code inside, stop with the index issue for now.
Please try to understand why your batch is running so much, ask yourself questions like if there are big sort of data or if there are big joins with derived tables, check existing triggers on the updated tables, check if you have foreign keys toward other tables without indexes on those fields.
Also check if you run on a very large amount of data and trying to update all of them together in one transaction, if this is the case you should use a temp table with little chunks.
You see now the picture, don't run immediately to the indexes.
Tell me what you found, don't run to change the existing indexes !!