In my opinion, the lookup is unlikely to be the main culprit here. I'd be looking at the sorts and the OLEDB command - both notoriously slow and expensive. Can the sorts be done by the OLEDB source components? If so, get rid of the sort transforms.

Get rid of the OLEDB command component by sending all the no match output rows to a work table and have a final ExecuteSQL MERGE which does the work in a set-based fashion.