Physics explanation of charging time by increasing dielectric constant
Capacitance of a parallel place capacitor is related to the dielectric constant, area, and distance between plates by a very simple equation:

$$C = \frac{\epsilon_r \epsilon_0 A}{d}$$

Where \$C\$ is capacitance, \$A\$ is plate area, and \$d\$ is the separation between plates. \$\epsilon_0\$ is the permittivity of free space and \$\epsilon_r\$ is the relative permittivity.

The voltage across a capacitor at any given instant is given by:

$$V = \frac{Q}{C}$$

Where \$V\$ is voltage, \$Q\$ is the charge on the plates, and \$C\$ is the capacitance.

So clearly as capacitance increases, the amount of charge required for a given voltage across the plates will also increase proportionally. 

If you require more charge, it will take longer to reach a given voltage if you have the same initial current - which in an R-C circuit is governed by the resistor. In essence at time \$t=0\$, if there is no charge on the capacitor, all of the voltage is across the resistor, so this sets the maximum current. As the capacitor charges, the voltage across the resistor will decrease (it increases over the capacitance), so current decreases (Ohms law).

Given that current is the rate of change of charge, then with the same limitation on current, it will take longer to charge the larger capacitor to a given voltage.