Danny, I am using Bitcoin Core, and have encrypted my wallet with a strong passphrase. Is having the passphrase sufficient protection even if someone else has my wallet.dat?
If the wallet was protected by a strong passphrase
BEFORE you backed it up (and the passphrase is not stored with the backup), then you are probably safe from anyone accessing (spending or stealing) your bitcoins with the lost backup. If you set the passphrase
AFTER you backed up the wallet, then the backup can still access the bitcoins even without the passphrase.
Note, that if the backup is protected by a strong passphrase, this only protects you from someone using that wallet backup to spend or steal your bitcoins. It does NOT keep them from seeing how many bitcoins you have.
Would changing my passphrase increase my security
No. Changing your passphrase only changes access to the current wallet. It does not change access to the backup.
should I just follow the steps you laid out?
There are two risks you need to decide between.
Risk 1The person that finds your lost backup guesses your password or runs a program that tries many possible passwords until they stumble across yours. The stronger your passphrase, the lower this risk. If your passphrase is "password", then there is a good chance that your bitcoins will be stolen. If your passphrase is "afwY$CA9Yh8afN94o#8h^awf;ohiaf a409 a08aw4y p2($", then you don't have as much to worry about.
Risk 2You make a mistake in the process of creating a new wallet and sending the balance to the newly created wallet. Your mistake causes you to permanently lose access to your bitcoins.
Only you know your passphrase, and only you know your technical aptitude. So, only you can decide which is the greater risk.