I am using a Nexus 5 running Android 5.0.1, with adb version 1.0.32, on OS X 10.10.1.
When I reboot the device, on the initial screen I see:
USB debugging connected
Touch to disable USB debuggingI swipe up to unlock and then see the dialog:
Allow USB debugging?
The computer's RSA key fingerprint is: <....>
 Always allow from this computerI check always allow and tap OK.
If I reboot the device, I see the exact same thing again. I assume I should not be asked again and again to trust the same computer after a simple reboot.
Can anyone point me to a detailed description of how this system works so I can determine what is going wrong?
I believe the key identifying the computer is stored in the device in the data directory. I assume that a key would be stored on the computer as well. What is this location?
Is there anything else I can check?
Has anyone seen this before? If so, what was done to resolve the problem?