What happens to the public and private keys after a transaction? Specifically, how (and why) do they change upon payment?

TL;DR: Private and public keys never change by themselves. It is wallet software that chooses to rotate them.

Every private key gives rise to exactly one public key, which corresponds to one(*) address. The flow generally is:

• Receiver Roy creates an address:
  • generates a private key d
  • computes the public key P for d
  • computes the address A for P
  • gives the address A to the sender Sue
• Sender Sue sends money to Roy
  • constructs a transaction T1 that sends to A, using her private keys
• Roy wants to use the money sent to A to pay merchant Mary:
  • Roy constructs a transaction T2, which refers to T1's payment to A, and sends to an address received from Mary, and signs it with private key d.

Roy can choose to use the private key d multiple times, by giving out the address A for multiple intended incoming payments. Spending the money received from those payments would then involve signing multiple transactions with the same private key d.

While there is no technical reason preventing this practice (called address reuse), it is strongly discouraged for privacy reasons. The address A is visible on-chain, and thus reuse would help those Roy transacts with correlate the different payments with each other. Because of this, most (but not all) wallet software will show every receiver address just once.

This is purely a decision by the receiver's wallet. Due to how Bitcoin's transactions and addresses work, there is no financial benefit to using a new address for every transaction as opposed to reusing the same every time. Fees do not depend on whether the address was reused or not.

Most modern wallet software derives the different private keys d₁, d₂, ... using a key derivation algorithm, from a single seed or master key. That means the wallet only needs to (securely) store one piece of information from which all keys can be derived. However, while all keys come from the same seed, the public cannot infer this anymore from the corresponding addresses. Common standards for this derivation include BIP32 and BIP39.

(*) It is possible to generate multiple addresses from the same public key due to Bitcoin's script system, though not in a way that really matters for this answer, as such addresses can still be correlated to each other. E.g. it is possible to construct P2PKH, P2WPKH, or P2TR addresses from one key, corresponding to different script technologies. Typically wallets will just use one of these, however.

Disclaimer: I'm the author of BIP32.

You can get bonuses upto $100 FREE BONUS when you:
💰 Install these recommended apps:
💲 SocialGood - 100% Crypto Back on Everyday Shopping
💲 xPortal - The DeFi For The Next Billion
💲 CryptoTab Browser - Lightweight, fast, and ready to mine!
💰 Register on these recommended exchanges:
🟡 Binance🟡 Bitfinex🟡 Bitmart🟡 Bittrex🟡 Bitget
🟡 CoinEx🟡 Crypto.com🟡 Gate.io🟡 Huobi🟡 Kucoin.