The automatically generated key is called the debug key/certificate.
You should generate a new key can just copy it over to both your devices. The only negative of this is your builds process is longer as you need a manual steps.
The other option is to copy over the debug key from one of the systems.
You will find the keys in a folder names
.android in your home directory in Linux & user directory in Windows
Tip: Never loose the certificate once you push an app to the market.
In Unix like os the debug key is located by default in
You also can choose a custom one from eclipse like in the following screenshot: