The search for the insert location is O(log(N)). Next you have to make a new dict and copy the data. Copying the data are two simple memcpy() calls (the part before the new key and the part that follow it). So, yes, insert in O(n), but the constant factor is pretty low.
Long time I did a comparison with rbtrees and If I recall correctly rbtrees started to win around 1,000 k-v pairs. May have changed a bit. In other words, used for representing compound data structures they are typically fine. They are not suitable to implement (for example) word-counting a document using for each word, update the count in the dict by one. The way to implement that is to make a flat list of words, use sort/4 (or msort/2) to sort while keeping duplicates and walk over the list to establish the counts. Next you can do dict_pairs/3 to create a dict for subsequent lookup if an on-stack data structure is desirable.