So doing a "deep dive" on this now that I'm aware that DEFAULT_ADB_ALLOWED_CONNECTION_TIME
exists.
Lets take a look at the Android source:
This "security" feature is most certainly a thing. It was added in Android 10.
https://cs.android.com/android/_/android/platform/frameworks/base/+/9e7b06efe38977cc083964700f2459b175380c69
public static final long DEFAULT_ADB_ALLOWED_CONNECTION_TIME = 604800000;
/**
* When the user first connects their device to a system a prompt is displayed to allow
* the adb connection with an option to 'Always allow' connections from this system. If the
* user selects this always allow option then the connection time is stored for the system.
* This setting is the time in ms within which a subsequent connection from an always
* allowed system is allowed to reconnect without user interaction.
...
*/
From the above, the default for this is 7 days. Note: this is 7 days from the last successful connection, not 7 days from the initial connection.
A configuration option for this was added to the UI in 2020, I'm not sure what version of Android that corresponds with. Perhaps this explains the assumption that it's Android 12 related even though it existed prior to that.
https://cs.android.com/android/_/android/platform/packages/apps/Settings/+/3d8974723a2f6b11eafbcbac0229d363021de877
Implementation:
https://cs.android.com/android/platform/superproject/main/+/main:frameworks/base/services/core/java/com/android/server/adb/AdbDebuggingManager.java
The public keys are actually being stored in a secure Android KeyStore. If keys exist in /data/misc/adb/adb_keys
they are automatically added to this keystore as needed.
With every connection, the stored "last connection time" attribute is updated for the associated key within the KeyStore. In addition, there is a background process that runs once a day to update the "last connection time" for any persistent connections.
Now with all this being said, I'm still unsure how to explain how I was able to take an Onn device out of the closet that hadn't been used in six months and connect without a prompt. 
AH4C shells out to the cli version of adb which maintains an active connection. ADBTuner closes connections after each action. This probably explains why the popups were more common in ADBTuner even though the issue should technically affect both.
TLDR;
Hopefully this configuration change does help with devices that aren't used at least once a week. I think there might be some other things that might be causing failed authorizations, but this is a good start. Thanks @tmm1 for the heads up.