Now I just think this is going to be an issue!
I thought having a backup of my wallet on USB and printing my private keys to a paper is safe
That is a very bad assumption if you are using bitcoind. There are other wallets where that would be true.
But apparently every time I spent, there is a new private key generated.
Correct.
So I need to backup this new updated wallet and reprint my list of private keys.
Not exactly. bitcoind pre-generates the next 100 private keys and addresses that it will use. All of these "future use" private keys are stored in the wallet.dat. When bitcoind needs a new address for the "change", it gets the next address from this pre-generated list, and then generates a new address to add to the other end of the list.
This means that the backup that you have of wallet.dat is good for the next 100 addresses that the wallet uses (keeping in mind that an address is "used" each time you ask the wallet for a new receiving address, AND each time you send a transaction.
This size of this pool of pre-generated addresses can be adjusted with a setting in bitcoin.conf
If you are using bitcoind, and printing (or writing) private keys, and creating transactions, then yes your written private keys will become useless as soon as you send a transaction.
Let's assume I made a paper wallet and transferred 1 BTC to it and gave it to my friend.
Then later, he spent 0.1 BTC on something by using the private key printed on that paper.
Little did he know, his wallet is now empty and useless, since there is 0.9 BTC change had been "refunded" to a different address with different private key.
Anytime you import a private key to a wallet, you should immediately consider the private key to be compromised and stop using it. If you still want a paper wallet, then you should create a new one and send any balance there. If you don't know enough about private keys to know this, then you don't know enough about private keys to use them safely, and should not be creating paper wallets in the first place.
The question is
Why does the transaction not give the change back to the same output address?
Increased privacy, and increased security.
Satoshi specifically stated in the Whitepaper that introduced the concept of bitcoin to the world that users should create a new address for EVERY transaction. Then, when he released his client software, he had written it to do exactly that.