Atrocious performance joining INSERTED and DELETED tables in a trigger
You could evaluate using explicit INNER MERGE JOIN or INNER HASH JOIN hints but given that you are presumably using these tables again later in the trigger you are probably better off just inserting the contents of inserted and deleted tables into indexed #temp tables and being done with it.

They do not get useful indexes created for them automatically.