It looks like 12% of the time is being spent figuring out what rows to insert, and 88% actually doing the insertions.
So I think that index maintenance is killing you. You could try adding a sort to your select so that rows are inserted in index order, or inserting in batches in which the batches are partitioned by service_id (which is almost the same thing as sorting, since service_id is the lead column)
