Just because you have used Entity Designer to start with doesn't mean that you have to totally recreate your database each time.
If you generate the SQL from your changed model, you should be able to find the part referring to your new relationship easily enough. That is the only part you need to run against your database- just split it out into it's own file. If in doubt save a copy of the old SQL file, add your relationship, generate the new file and create a diff to be sure.
Alternatively if you have a good understanding of how EF represents data and relationships you can probably change the database manually. As long as the database and the model are accurately coherent, EF doesn't really care how the database got that way.