Upgrades classically take a long time. Particular from NAV 2009 to NAV 2013 as there were significant changes to the way Dimensions work.
The update routine has to generate new Dimension Set ID's to represent every combination of dimensions, and then tag the associated records accordingly. It's a lot of processing, but makes Dimensions faster and better suited for longevity.
Database
Assuming you can take a full backup before running the transfer, you could disable the FULL logging to say, SIMPLE. Though this will technically still log, it will manage space itself.
Making sure your database files are split out correctly is important for best performance (including master > tempdb).
Indexes & Keys
I'd guess that Microsoft would have significantly optimised the dimension tables (key wise). It was a big change to dimensions in NAV 2013. That being said, it might be worth disabling the indexes on the table (where possible) as that can impact write performance.
Upgrade Toolkit
The upgrade toolkit (from memory) actually executes raw SQL to transfer large data. If you're able to, it might be worth looking through the code of the upgrade toolkit to see whether you can run it directly in SQL yourself (though you mentioned you can't change the query?).
Jump into PartnerSource to see if there are any application hotfixes by Microsoft that might optimise the Upgrade Toolkit, though it's been out for several years so it may be quite settled.
Alternate Queries
Check on Mibuso (for example) to see if there are some user-written queries that might optimize the migration to NAV 2013, obviously take caution with these alternate scripts and test them thoroughly before running in LIVE.
Deleting Data
The core reason that the upgrade takes so long is that there is a heap of data to migrate, especially systems that are several years old. You could potentially delete the dimension data for entries older than a set period (e.g. 4 years), though this will mean the data can no longer be analysed with existing dimension-based reports, etc.