How does relative permittivity decrease with frequency while capacitance doesn't?
Here's an example of measured capacitance change with frequency (10uF MLCC with X5R dilectric) :-

 

Note that the capacitance measurement only goes up to the capacitor's resonant frequency, because above resonance it becomes inductive.   

Now here's the impedance change with frequency. This graph is logarithmic on the y axis, so the actual change is greater than it looks.   



Over a 3 decade range from 1kHz to 1MHz the capacitive reactance varies by a ratio of 1000:1, while the capacitance is almost constant. 

At low frequencies the permittivity of many dielectrics is practically constant, which is why it might be said that capacitance isn't affected by frequency, but capacitive reactance is.  

However at some higher frequency (well above the working frequency range of this capacitor) the permittivity of most dielectrics drops as their response changes from ionic/dipolar to atomic and then to electronic scale. The curve depends on the particular material's atomic structure, and the formula for calculating it is not simple.   

Permittivity