Show $\sum_{k=0}^{p-1} \left(\frac{k^2+1}{p}\right) = \sum_{t=0}^{p-1} \left(1 + \left(\frac{t}{p}\right)\right)\left(\frac{t+1}{p}\right)$

Question

Let $p$ be an odd prime. I wish to show that $$\sum_{k=0}^{p-1} \left(\frac{k^2+1}{p}\right) = \sum_{t=0}^{p-1} \left(1 + \left(\frac{t}{p}\right)\right)\left(\frac{t+1}{p}\right),$$ where the notation $\left(\frac{a}{b}\right)$ represents the Legendre symbol.

For any fixed $0 \leq t \leq p-1$, I know that there are $1 + \left(\frac{t}{p}\right)$ corresponding $k$'s for which $k^2 \equiv t \pmod{p}$ and hence $k^2 + 1 \equiv t + 1 \pmod{p}.$ But I am unsure how to relate this observation to the proof of the above equality.