It is because of collisions. ConcurrentDictionary maintains a list of buckets and the result returned by GetHashCode method determines in which bucket an entry will be placed. Ideally each entry should be in the seperate bucket. However, in practise it is not possible. If GetHashCode returns the same value for 2 different keys, the collision appears and more and more entries is placed in the same bucket.
Under the hood, each bucket is implemented as the linked list. Every time, when the collision is detected a dictionary has to scan some linked list in order to check if a given entry is already there. The more elements is in this dictionary, the longer linked lists will be and the more time will be required to iterate through them.
By the way, standard Dictionary is implemented in the different way but will behave in the similar manner. The nice description of internals of both data structures can be found here