The best way I know how is to backup the database.
Break the relationships. Add new fields for the primary and foreign keys.
In an update query join the old primary and foreign keys and update the new
foreign key field with the new primary key.  Re-build the relationships.

If your old primary key is usable, you can (with some hassle).

BACK UP YOUR DATABASE first, you'll be taking a chainsaw to the design!

Add an autonumber ID to the main table as primary key. You'll probably want to
create a new empty table with all the fields of the old, plus the new
Autonumber; run an Append query to migrate your data into the new table (sort
by the old ID if the order of records is important to you).

Add a Long Integer foreign key to each related table. DON'T join them yet!

Now run as many Update queries as you have child tables. Join the (new) main
table to each child table by the *old* ID; update the foreign key field to the
new autonumber field.

Then, delete all the relationships on the old ID, and establish new
relationships from the autonumber to the foreign key.

If the old key is "human meaningful", or if it has appeared in printouts and
may be needed in the future, leave it in the main table, but I'd say remove it
from the child tables.

Test all your forms and reports. Swear, grumble, groan and fix the errors that
you will find. Iterate until done.

Good luck - this is probably a Good Thing to Do but it can be a real hassle!

            John W. Vinson [MVP]