Options for deleting millions of inactive Contacts

We are currently running Kentico 12SP in Azure with Contacts in a separate database. The Delete inactive contacts scheduled task was not running for about 2 years due to errors that could not be resolved at that time. Since then, we accumulated 10's of millions Contacts and 100's of millions Activities, and recently had to add storage capacity to the database. The scheduled task is now working properly, and we need to delete the stale/inactive Contact data to reduce the size of the database and improve performance. However, the rate at which it deletes inactive contacts (1,000/execution/site) will not keep up with the daily growth, much less shrink the database.

I understand that we can write a custom scheduled task by creating a class that implements the IDeleteContacts interface, but the stored procedure it calls [Proc_OM_Contact_MassDelete] is slow - it took over 14 minutes to delete 4,000 Contacts (1,000 x 4 sites). While ~0.2 seconds/Contact doesn't seem too bad, it adds up fast when you have millions of Contacts - we're looking at about 2,000 hours if it ran continuously.

I'm hoping we can find a faster solution.