It’s worth considering if you’re using the wrong data structure, rather than trying to optimize the update process of a possibly sub-optimal representation. (Transformation of the existing data structure back and forth to another representation can be a “tell”.) Designing the data structure around your desired interactions with it (instead of picking the data structure then designing its programmatic interface after the fact) often makes hairy update problems like this melt away.
Maybe an ordered map could help? https://github.com/clj-commons/ordered#maps
Or, if the problem is better identifying the element to change, is there a reason not to add a unique id key to each element, and use that instead of possibly-duplicate keys?
Lastly, to contradict my own advice above, libs like specter can make it straightforward to update a particular thing in a heterogenous nested structure like you describe. But I often find that I prefer solving such problems by simplifying the data structure 