The best way is make your own database which have column address and amount. There's big bottleneck if you use Bitcoin Core or block explorer API.
Combining your script with tools mentioned by @seoincorporation and query to local database would save lots of time.
And the second step is the complex one... Verify the address balance, for this, you can use an API from some block explorer to verify if the address has balance, or another way is to do it directly with bitcoin core.
Bitcoin Core don't index balance of each address, unless it's part of your wallet (including watch-only address). You could use chainstate and txindex though.
But i think the best way to do it and to save time is to import all those private keys to bitcoin core, that way you will not waste time calling the API to verify if they have balance or not.
I'm not sure if it's best way when we're talking about hundred thousand of Bitcoin address.
I think bitcoin core was able to show balance but as you say for that we have to add the address as watch only...
And about the best way you are right, is not the best way, is just the easy way.
I reply again because i found the python script i used in the past for the same propose, it's called coinkit:
from coinkit.keypair import BitcoinKeypair
k = BitcoinKeypair('5Jx4txgXUCe1kP8mBLEZrLSsZm9WRin8xijWvVW8RACzHn2ZzBH')
d = k.address()
print (d)
For more information look at:
https://github.com/mflaxman/coinkit