You don't need the recovery key to access the account, only the password. If the password was compromised it could not be changed. This seems less secure regardless of anyone having the recovery key.
That's why you should have multiple trusted devices (as recommended by Apple)
Which SMS numbers should I verify for my account?
You're required to verify at least one SMS-capable phone number for your account. You should consider verifying all SMS-capable phone numbers that you normally use with your iPhone or another mobile phone. You should also consider verifying an SMS-capable phone number used by someone close to you, such as a spouse or other family member. You can use this number if you're temporarily without access to your own devices.
you could then reset your recovery key and remove the stolen phone as a trusted device which would render the two things in the possession of the thief useless for accessing your account.
If, for some reason you can't register multiple devices then keep multiple copies of the recovery key in different places (which is a good idea anyway, as recommended by Apple)
Keep your Recovery Key in a secure place in your home, office, or other location. You should consider printing more than one copy, so that you can keep your key in more than one place. Your key will be easier to find if you ever need it, and you'll have a spare copy if one is ever lost or destroyed.
You shouldn't store your Recovery Key on your device or computer, because that could give an unauthorized user instant access to your key.
and you can then use this key and your password to reset the trusted devices and recovery key and again render the stolen items useless for accessing your account.
Apple do give very clear warnings about this
What do I need to remember when I use two-step verification?
Two-step verification simplifies and strengthens the security of your Apple ID. After you turn it on, there's no way for anyone to access and manage your account other than by using your password, verification codes sent to your trusted devices, or your Recovery Key. Only you can reset your password, manage your trusted devices, or create a new Recovery Key. Apple Support can help you with other aspects of your service, but they aren't able to update or recover these three things for you. Therefore, when you use two-step verification, you are entirely responsible for:
Remembering your password
Keeping your trusted devices physically secure
Keeping your Recovery Key in a safe place
If you lose access to two of these three items at the same time, you could be locked out of your Apple ID permanently.
All quotes from this page: http://support.apple.com/en-gb/HT5570