I have just looked at my RAC cover and to be honest the list of exclusions is baffling. It used to be much simpler before they were taken over by Aviva. Before then it was for members benefit, not shareholders. If you have roadside only, they will transport you and your vehicle up to ten miles but only if you are 'broken down' and they cannot repair at the roadside. I cannot see anywhere in the policy about lost keys. Give them a ring and ask where in the policy document does it say that you are not covered. I broke my key in the lock once (a long time ago) and they sent out a locksmith who made up a new key on the spot.
If it turns out they are correct, check you car insurance. You may be covered under that.