If you have offline sessions you actually can detect a device for a kind of infinite time.
Maybe some kind of unprivileged offline session which does not represent real access rights but rather the information that this is a known device would help. Like some kind of special client "device" which only exists to create this "device sessions" for this client on any device a user could have...

Yes, a device is identified as new if it can't be recognized either by a information provided by the browser (i.e. user agent info or other fingerprinting techniques) or by a cookie which was placed there before by Keycloak. It could also be a combination. I would like to discuss and understand which information is extracted and stored client (browser) and server-side to identify a client.

A simple logic would be a cookie so that a device is always a new one when this cookie isn't send. This is probably the 'magic signed cookie on the device' @stianst talked about in the KEYCLOAK-4124 comment. This also lists the idea to have new kind of sessions.

I like the idea to have a new event when a new device is detected. I think the part 1 could be sufficient in a first step allowing users to write a SPI handling this event.
About the parsing of UserAgent to display information to the user, perhaps a new library is not needed as the class DeviceActivityManager seems to already do someting very similar ? Maybe a DeviceRepresentation could be added in the event ?