How do I replace a trusted phone number with a new one for iCloud account recovery?

Trusted devices and trusted phone numbers are 2 different things.

When you sign in to your Apple Account on a new device, that device becomes a trusted device.

This has. nothing to do with any Trusted phone numbers you may have added to your account, and in fact the trusted phone number should always be a different phone number you have access to even when you don't have access to your iPhone.

The Trusted phone number is a backup fail safe when you don't have your trusted devices available to get the Two-Factor authentications codes. In that case, you can have a code sent via SMS or voice call to a trusted phone number so you can log in to your account on a different device or computer.

A Trusted phone number can be an Android device or a landline of someone you trust or even your own home line if you have one.

You can update trusted phone numbers through your Apple Account from a trusted device or the https://account.apple.com website.

click here ➜ Two-factor authentication for Apple Account - Apple Support