Check this:
Dim oDict As Dictionary(Of Integer, Integer) = New Dictionary(Of Integer, Integer)
oDict.Add(123, 3)
oDict.Add(345, 21)
oDict.Add(22, 0)
oDict.Add(56, 1)
oDict = oDict _
.OrderBy(Function(x) x.Key) _
.Select(Function(x, i) New KeyValuePair(Of Integer, Integer)(x.Key, i)) _
.ToDictionary(Function(kvp) kvp.Key, Function(kvp) kvp.Value)
Good luck!