Perhaps this can be built out of smaller data structures.
Clearly the representation [k1, v1; k2, v2; ...; kn, vn] is a map with the property, but most operations are in the order of O(n) and thus wholly unsatisfactory for any map with more than, say, 500 elements.
If you don't need persistence, my intuition would be to use Janes St. Core and then build it out of Doubly_linked and Map from Core. The idea is that the map values are elements of the doubly linked list, we wrap Map and maintain the DL list as well. Then the insertion order can be handled by the DL list, so asking for the ordered keys is just walking the list in the direction desired. This keeps the asymptotics of the Map since operations on the DL list are O(1).
There might be a direct implementation of this idea, but I'll defer that to people who write OCaml on a daily basis :)
If you *do* need persistence, one way is to keep two maps. One maps a sequence number to a key. The other maps a key to a pair of a sequence number and a value. The triple of (sequence_no, order_map, map) should be persistenly maintainable, under the price of a factor 2 efficiency loss.
Better (functional) data structures may exist for this problem, but I don't know about them from memory alone.