could it be the starter?

Learn to troubleshoot, HERE is how this works

Relay is an electromagnet activated by the key. The functional path is "key in start"----wire to one of two "push on" flag terminals on the relay. This is one terminal of the coil

Through the coil, out the remaining flag terminal, and to ground if it's a stick, and down a wire to the neutral safety switch if it's automatic. The NSS grounds the coil if in park or neutral.

Battery is always "hot" to the Great Big Stud on the relay. This is one relay contact and a handy battery junction point.

When the relay pulls in (key in start) the contacts close, sending battery power out the "big square" terminal. This is a large gauge wire and only goes to one place.........the starter solenoid, causing the solenoid to pull in and activate the starter

Trouble spots.........Even though the relay clicks, the contacts can be rusty/ corroded/ burned and not "make."

The wire to the solenoid can be open. THESE USED TO VIBRATE from engine movement down near the starter.......it happens.

The main battery cable can be bad.......and you changed that.

Start by (transmission in park or neutral) jumper the two largest terminals on the starter relay. If it cranks, the relay is at fault, because you can hear it click.

If it does not crank, or makes no noise from the starter, you are back to battery / cable connections, or just plain a BAD STARTER