Near-linear growth conjecture for the theta-function arithmetic sum

For positive integers $h$ and $k$, define

$$S(h,k):=\sum_{j=1}^{k-1}(-1)^{j+1+\lfloor hj/k\rfloor},$$

where $\lfloor x\rfloor$ is the greatest integer less than or equal to $x$, and define

$$S(k):=\sum_{h=1}^{k-1}S(h,k).$$

Let $C_1$ and $C_2$ be any fixed positive numbers, and let $\epsilon>0$ be fixed. Near-linear growth conjecture. For all sufficiently large primes $k$,

$$C_1k<S(k)<C_2k^{1+\epsilon}.$$

The conjecture is motivated by numerical fits suggesting growth slightly greater than linear, with an observed best-fit slope of approximately $5.7$. It asserts a linear lower bound and an upper bound arbitrarily close to linear up to the factor $k^\epsilon$, but remains unproved.