Stochastic heating refers to an increase in the average magnetic moment of charged particles interacting with electromagnetic fluctuations whose frequencies are smaller than the particles' cyclotron frequencies. This type of heating arises when the amplitude of the gyroscale fluctuations exceeds a certain threshold, causing particle orbits in the plane perpendicular to the magnetic field to become stochastic rather than nearly periodic. We consider the stochastic heating of protons by Alfv\'en-wave (AW) and kinetic-Alfv\'en-wave (KAW) turbulence, which may make an important contribution to the heating of the solar wind. Using phenomenological arguments, we derive the stochastic-proton-heating rate in plasmas in which $\beta_{\rm p} \sim 1-30$, where $\beta_{\rm p}$ is the ratio of the proton pressure to the magnetic pressure. (We do not consider the $\beta_{\rm p} \gtrsim 30$ regime, in which KAWs at the proton gyroscale become non-propagating.) We test our formula for the stochastic-heating rate by numerically tracking test-particle protons interacting with a spectrum of randomly phased AWs and KAWs. Previous studies have demonstrated that at $\beta_{\rm p} \lesssim 1$, particles are energized primarily by time variations in the electrostatic potential and thermal-proton gyro-orbits are stochasticized primarily by gyroscale fluctuations in the electrostatic potential. In contrast, at $\beta_{\rm p} \gtrsim 1$, particles are energized primarily by the solenoidal component of the electric field and thermal-proton gyro-orbits are stochasticized primarily by gyroscale fluctuations in the magnetic field.