For carbon steel alloys higher strength generally correlates with lower corrosion resistance. This is especially true for galvanic corrosion where high strength fasteners tend to be anodic to the low strength structures of same material that they are connecting. This is a serious problem due to the large ratio of structure steel to fastener steel.
As Tugboateng stated, higher hardness typically means higher corrosion rates.
NACE MR0175 is an example of how low hardness can be used to limit corrosion. Of course, if your corrosion risk is not SCC/SSC, then MR0175 is not directly applicable but it shows how important hardness can be.
There are number of surface treatments that result in an oxidized surface Tath is usually black or blue.
These offer a little bit of corrosion resistance.
But they are very good at retaining oils which will help corrosion resistance.