Assuming you havent done this yet, go to the dealership.
Inside the lock cylinder are the "gates" that are set at certain heights defined by a number, IIRC its 1-6 or something like that. They can pull those "gates" one at a time, and determine what the number code is for the key that will work with them. they can then cut a key (or set of keys) to match that number designation.
pretty much the same thing the locksmith would do, i wouldnt hazard a guess as to which would be more expensive.
but either way, it would avoid needing to replace the locks on all the doors.